【poj 1961】Period（字符串--KMP 模版题）
题意：给你一个字符串，求这个字符串到第 i 个字符为止的重复子串的个数。
解法：判断重复子串的语句很重要！！if (p && i%(i-p)==0) printf("%d %d ",i,i/(i-p));
我之前一直不是很理解，而实际上多枚举几种情况就好了。若是重复的，那么next[i]肯定是最大值，值余下一个循环节不同；而若不是，next[i]表示的前缀和后缀串的和重叠部分不一样以外的部分就肯定空出来，不能整除的。（P.S.我在说些什么......ｍ（．＿．）ｍ）
因此，最小重复子串就是 i-next[i]，最大重复子串就是 next[i]。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 7 const int N=1000010; 8 int next[N]; 9 int n; 10 char s[N]; 11 12 void kmp() 13 { 14 memset(next,0,sizeof(next)); 15 int p=0; 16 next[1]=0; 17 for (int i=2;i<=n;i++) 18 { 19 while (s[i]!=s[p+1] && p) p=next[p]; 20 if (s[i]==s[p+1]) p++; 21 next[i]=p; 22 if (p && i%(i-p)==0)//p 23 printf("%d %d ",i,i/(i-p)); 24 } 25 } 26 int main() 27 { 28 int T=0; 29 while (1) 30 { 31 scanf("%d",&n); 32 if (!n) break; 33 scanf("%s",s+1); 34 if (T) printf(" "); 35 printf("Test case #%d ",++T); 36 kmp(); 37 } 38 return 0; 39 }