# POJ 2406 Power Strings C语言版

POJ题解 2118浏览

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

Slyar:说一下题目大意。a是一个字符串，记s=a^n为a重复n次所形成的字符串。比如说a是abcd，那么当n=3时，a^3就是abcdabcdabcd。现在给出字符串s，求出最大的重复次数n。

//www.slyar.com/blog/kmp.html

```#include
#include

#define MAX 1000001

int next[MAX];
char s[MAX];

int main()
{
int i, j, n, k, len;
while(1)
{
scanf("%s", s);
if (strcmp(s, ".") == 0) break;
len = strlen(s);
i = 0;
j = -1;
next[0] = -1;
while(i < len)
{
if (j == -1 || s[i] == s[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
/* 计算首尾重复子串的长度 */
j = i - next[i];
printf("%d %d %d\n", i, next[i], j);
/* 若串满足重复性质，则i%j==0；否则重复子串为本身 */
if (i % j == 0) k = i / j;
else k = 1;
printf("%d\n", k);
}
return 0;
}
```