思路：KMP算法。还记得KMP算法中next数组的含义吗。假设next[i]=x，就表明字符串前i个字符的子串中前x个字符和后x个字符是完全相同的。对于一个周期串来说，假设它的长度是len，最小周期是p，那么它的前len-p个字符和后len-p个字符是完全相同的。那么我们只需要求一次next数组，就可以掌握字符串的所有前缀的周期情况了。
这里的next的求法就是最原始的那种，没有优化，因为他是比较自身循环次数，所以不需要进行优化去除不匹配的特殊情况
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; const int maxn=1000000+5; int next[maxn]; int num; void getnext(string p) { int plen=p.size(); int k=-1; int j=0; next[0]=-1; while(j<=plen-1) { if(k==-1||p[j]==p[k]) { j++; k++; next[j]=k; } else k=next[k]; } } int n; void zhuan(string in) { for(int i = 1; i < n; i++)//动态规划求next数组 { int j = i; while(j != 0) { j = next[j]; if(in[j] == in[i]) { next[i + 1] = j + 1; break; } } } } int main() { string s; int n; int k=0; while(cin>>n&&n) { cin>>s; k++; getnext(s); // for(int i=0;i<n;i++) // cout<<next[i]<<endl; //zhuan(s); // for(int i=0;i<n;i++) // cout<<next[i]<<endl; cout<<"Test case #"<<k<<endl; for(int i=0;i<=n;i++) { if(i%(i-next[i])==0&&next[i]&&i/(i-next[i])>=2) cout<<i<<" "<<i/(i-next[i])<<endl; } cout<<endl; } return 0; } 但是用next应该会报CE
改成了nextt
其实kmp还是蒙蒙的，所以升级版ac自动机过几天再补
