# POJ2406 Power Strings(KMP)

 Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 56162 Accepted: 23370

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
kmp的经典应用

```#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1e6 + 10;
char s[MAXN];
int fail[MAXN];
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
//freopen("a.out", "w", stdout);
#endif
while(scanf("%s", s + 1) && s != '.') {
int N = strlen(s + 1), now = 0;
for(int i = 2; i <= N; i++) {
while(now && s[i] != s[now + 1]) now = fail[now];
if(s[i] == s[now + 1]) now++;
fail[i] = now;
}
if(N % (N - fail[N]) == 0) printf("%d\n", N / (N - fail[N]));
else printf("1\n");
}
return 0;
}```

原文作者：自为风月马前卒
原文地址: https://www.cnblogs.com/zwfymqz/p/9255867.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。