Power Strings poj2406（神代码）

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 char a[1100000];
 6 int t;
 7 int main()
 8 {
 9     char x;
10     while(1)
11     {
12         t=0;
13         x=getchar();
14         if(x==‘.‘)break;
15         while(1)
16         {
17             a[t++]=x;
18             if(x==‘\n‘)break;
19             x=getchar();
20         }
21         int p=1,k=1;
22         t--;
23         for(int i=0; i<t; i++)
24         {
25              if(a[i]==a[i%p])
26              k++;
27              else
28              {
29                  if(p==k)k++;
30                  p=k;
31              }
32         }
33         if(t%p==0)
34         printf("%d\n",t/p);
35         else printf("1\n");
36     }
37 }

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 char a[1100000];
 6 int t,next[1100000];
 7 void fun()
 8 {
 9     next[0]=0;
10     int i,j=0;
11     for(i=1;i<t;i++)
12     {
13         while(j>0&&a[i]!=a[j])j=next[j-1];
14         if(a[i]==a[j])j++;
15         next[i]=j;
16     }
17 }
18 int main()
19 {
20     char x;
21     while(1)
22     {
23         t=0;
24         x=getchar();
25         if(x==‘.‘)break;
26         while(1)
27         {
28             a[t++]=x;
29             if(x==‘\n‘)break;
30             x=getchar();
31         }
32         t--;
33       fun();
34       if(t%(t-next[t-1])==0)
35       printf("%d\n",t/(t-next[t-1]));
36       else printf("1\n");
37     }
38 }