Power Strings poj2406（神代码）

Power Strings

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 29402		Accepted: 12296

Description

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

两种做法：

 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=='
')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
",t/p);
35         else printf("1
");
36     }
37 }

View Code

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==' ')break; 30 x=getchar(); 31 } 32 t--; 33 fun(); 34 if(t%(t-next[t-1])==0) 35 printf("%d ",t/(t-next[t-1])); 36 else printf("1 "); 37 } 38 }

Power Strings poj2406（神代码）

相关推荐