对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串
n-fail[n]
fail[n]>n/2时，循环节的性质
fail[n]<n/2时，要满足不断连接的话就只能n-fail[n]那么长了
1.循环节移位一下仍是循环节
2.循环节重叠后会自我重复
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=1e6+5; int n,fail[N]; char s[N]; void getFail(){ fail[1]=0; for(int i=2;i<=n;i++){ int j=fail[i-1]; while(j&&s[i]!=s[j+1]) j=fail[j]; fail[i]=s[i]==s[j+1]?j+1:0; } } int main(){ freopen("in.txt","r",stdin); scanf("%d%s",&n,s+1); getFail(); printf("%d",n-fail[n]); }
BZOJ 1355: [Baltic2009]Radio Transmission [KMP 循环节]
原文：http://www.cnblogs.com/candy99/p/6365872.html