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

abcdaaaaababab.

Sample Output

143

Hint

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

Source

 

 

kmp的经典应用

设$len$表示字符串的长度，$next[i]$表示$i$号字符串的最长公共前后缀的长度

如果$len \ mod  \  next[len] == 0$，那么循环节的长度为$n / next[len]$

 

#include
      
       #include
       
        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[1] != '.') {        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;}