Period HDU - 1358

题意&&思路：

基本和uva那道eg题一模一样。

Period UVA - 1328

AC

#include <iostream> #include <cstring> using namespace std; const int maxm=1e6+10; char p[maxm]; int m, nxt[maxm]; void getnxt(){ int i=0, j=-1; nxt[0]=-1; while(i<m){ if(j==-1||p[i]==p[j])nxt[++i]=++j; else j=nxt[j]; } } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int kase=0; while(cin>>m&&m){ cin>>p; getnxt(); cout<<"Test case #"<<++kase<<endl;//1" for(int i=2; i<=m; i++){ if(nxt[i]>0 && i%(i-nxt[i])==0)cout<<i<<' '<<i/(i-nxt[i])<<endl; } cout<<endl; } return 0; }