首页 > 代码库 > poj 2406 Power Strings

poj 2406 Power Strings

同上

 1 #include<cstdio>
 2 #include<cstring>
 3 #define N 1000005
 4 #define LL long long
 5 #define inf 0x3f3f3f3f
 6 using namespace std;
 7 inline int ra()
 8 {
 9     int x=0,f=1; char ch=getchar();
10     while (ch<0 || ch>9) {if (ch==-) f=-1; ch=getchar();}
11     while (ch>=0 && ch<=9) {x=x*10+ch-0; ch=getchar();}
12     return x*f;
13 }
14 int fail[N];
15 int main()
16 {
17     char ch[N];
18     while (scanf("%s",ch+1))
19     {
20         if (ch[1]==.) break;
21         int n=strlen(ch+1);
22         int fix=0;
23         for (int i=2; i<=n; i++)
24         {
25             while (ch[fix+1]!=ch[i] && fix) fix=fail[fix];
26             if (ch[fix+1]==ch[i]) fix++; fail[i]=fix;
27         }
28         int x=n-fail[n];
29         if (n%x) printf("1\n");
30         else printf("%d\n",n/x);
31     }
32     return 0;
33 }

 

poj 2406 Power Strings