poj 2406 Power Strings 周期问题

Power Strings

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

Hint

This problem has huge input, use scanf instead of cin to avoid time limit exceed.

Source

Waterloo local 2002.07.01

百度扯淡：

内存限制：时间限制：3000ms 65536k 意见：总48139 20040接受： 描述 我们给出两个字符串A和B是定义了他们的concatenation *。例如，如果A和B =“abc”，然后在“def”=“*（ABCDEF）”。如果我们想到的exponentiation concatenation繁殖，用非负整数的定义为：在正常的方式（0 =“”（空字符串）和（N + 1）=（n×公尺）。 输入 每个测试用例的输入线，代表的是一个可打印的字符，字符串）。S的长度将至少1百万的人物将不超过1。含周期线为最后的测试案例。 输出 你应该为每个打印最大的N，S = N次这样的一些字符串。

样本输入 ABCD AAAA ABABAB . 示例输出 1 4 3 提示 这个问题有巨大的投入，而不是使用scanf的CIN，避免超过时间限制。 源代码 当地的2002.07.01滑铁卢

假设 S 的周期大于 1。假设 S 存在周期 X，而且每 个周期的长度为 L。那么，我们有 S[1..n-L] = S[L+1…n]， 对于 i=n 来说，n-L 是一个合法的 j。 * 由于 P 数组所求的是所有 j 的最大值，所以只要判断 P[n] 即 可。如果 P[n] < n/2，则说明 S 不存在周期；否则最小的周期 长度为 n-p[n]，对应的周期为 n / (n – p[n])。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 char a[1000002];
 6 int p[1000002];
 7 void makep(int l)
 8 {
 9     memset(p,0,sizeof(p));
10     int j=0;
11     for(int i=1;i<l;i++)
12     {
13         while(a[i]!=a[j]&&j>0)
14         j=p[j-1];
15         if(a[i]==a[j])
16         j++;
17         p[i]=j;
18     }
19 }
20 void deal(int l)
21 {
22     int ans=1;
23         if(l%(l-p[l-1])==0)
24         ans=l/(l-p[l-1]);
25     printf("%d\n",ans);
26 }
27 int main()
28 {
29     while(scanf("%s",a)==1)
30     {
31         if(a[0]=='.')break;
32         int l=strlen(a);
33         makep(l);
34         deal(l);
35     }
36     return 0;
37 }