uva 1328

简单KMP：
 1 #include<cstdio>
 2 #include<cstring>
 3 #define maxn 1000009
 4 using namespace std;
 5 
 6 char s[maxn];
 7 int next[maxn],n;
 8 
 9 void getnext()
10 {
11     int j=-1,i=0;
12     next[0]=-1;
13     while(i<n)
14     {
15         if(j==-1||s[i]==s[j])
16         {
17             j++,i++;
18             next[i]=j;
19         }
20         else j=next[j];
21     }
22 }
23 
24 int main()
25 {
26     int ca=1;
27     while(scanf("%d",&n)&&n)
28     {
29         memset(next,0,sizeof next);
30         scanf("%s",s);
31         getnext();
32         printf("Test case #%d
",ca++);
33         for(int i=2;i<=n;i++)
34             if(next[i]>0&&i%(i-next[i])==0)
35                 printf("%d %d
",i,i/(i-next[i]));
36         puts("");
37     }
38     return 0;
39 }
View Code