POJ 2406 Power Strings（kmp）

POJ 2406 Power Strings（kmp）

Language: Default Power Strings Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 33335 Accepted: 13852

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

求一個串的最小周期

對於一個串，如果abcdabc 那麼next[len]=3,那麼len-next【len】就大於len/2,那麼len%(len-next[len])!=0;而對於一個周期串ababab next[len]=4,此時len-next[len]應該等於

最小串的長度，所以是不是有最小周期就可以用len%(len-next[len])是否為0來判斷，（個人理解，如有錯，請想告）

#include
#include
#include
#include
#include
#include
#include
#include

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)

#define eps 1e-8
using namespace std;
#define N 100005

char a[N];
int len,next[N];

void getfail(char *a)
{
	 int i,j;
	 len=strlen(a);
	 i=0;j=-1;
	 next[0]=-1;
	 while(i