【题解】POJ-2406 Power Strings

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.

样例输入

1
2
3
4
abcd
aaaa
ababab
.

样例输出

1
2
3
1
4
3

提示

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

思路

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
char t[mxn];
int nxt[mxn];

void getnxt(char* t, int m)
{
int i = 0, j = -1; nxt[0] = -1;
while (i < m)
{
if (j == -1 || t[i] == t[j]) {
i++, j++;
// if (t[i] == t[j])
// nxt[i] = nxt[j]; // next数组优化
// else
nxt[i] = j;
} else
j = nxt[j];
}
}

int main()
{
while(scanf("%s", t) && strcmp(t, "."))
{
int m = strlen(t);
getnxt(t, m);

int L = m-nxt[m]; // 最小循环节=原串长度-末位失配,L=len-next[len]
printf("%d\n", m%L ? 1 : m/L); // 循环周期T=len/L
}
return 0;
}