poj 2406 Power Strings【KMP】

<a target="_blank" href="http://poj.org/problem?id=2406">點選打開題目</a>

Power Strings

Time Limit: 3000MS

Memory Limit: 65536K

Total Submissions: 33548

Accepted: 13935

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

Sample Output

Hint

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

題目翻譯意：給一個字元串S長度不超過10^6，求最大的n使得S由n個相同的字元串a連接配接而成，如："ababab"則由n=3個"ab"連接配接而成，"aaaa"由n=4個"a"連接配接而成，"abcd"則由n=1個"abcd"連接配接而成。

解題思路：假設S的長度為len，則S存在循環子串，當且僅當，len可以被len - next[len]整除，最短循環子串為S[len - next[len]]

利用KMP算法，求字元串的特征向量next，若len可以被len - next[len]整除，則最大循環次數n為len/(len - next[len])，否則為1