字符串刷题

P4391 [BalticOI 2009] Radio Transmission 无线传输KMP 最小循环节: ansn-next[n], next数组中存储的是 第i 位字符串中最长相等的前后缀, i n时存储的当前字符串中最长的相等的前后缀。剪掉上一次循环的开始#include bits/stdc.h using namespace std; const int N 1000010; char s[N]; int n, ne[N]; int main(){ cin n s1; for(int i2, j0; in; i){ while(j s[j1] ! s[i]) j ne[j]; if(s[j1] s[i]) j; ne[i] j; } // 最小循环节公式n - ne[n] cout n - ne[n] endl; return 0; }