Power Strings (POJ-2406)

题面

Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “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).

输入

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.

输出

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

样例输入

1abcd
2aaaa
3ababab
4.

样例输出

11
24
33

提示

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

思路

KMP求最小循环节。输出最小循环周期。POJ提交时注意C++和G++的区别。

代码

 1char t[mxn];
 2int nxt[mxn];
 3
 4void getnxt(char* t, int m)
 5{
 6    int i = 0, j = -1; nxt[0] = -1;
 7    while (i < m)
 8    {
 9        if (j == -1 || t[i] == t[j]) {
10            i++, j++;
11            // if (t[i] == t[j])
12            //     nxt[i] = nxt[j]; // next数组优化
13            // else
14                nxt[i] = j;
15        } else
16            j = nxt[j];
17    }
18}
19
20int main()
21{
22    while(scanf("%s", t) && strcmp(t, "."))
23    {
24        int m = strlen(t);
25        getnxt(t, m);
26
27        int L = m-nxt[m];   // 最小循环节=原串长度-末位失配，L=len-next[len]
28        printf("%d\n", m%L ? 1 : m/L);  // 循环周期T=len/L
29    }
30    return 0;
31}