Description#

Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “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#

1
abcd
2
aaaa
3
ababab
4
.

Sample Output#

1
1
2
4
3
3

题解#

主要考虑 KMP 中失陪函数的意义
因为整个串是会重复的
所以整个串的长度一定是串长减最后一个字符的fail的倍数

1
#include<iostream>
2
#include<cstdio>
3
#include<cstring>
4
using namespace std;
5
const int N=1000005;
6
char S[N];
7
int next[N],len;
8
void get_next(){
9
    next[0]=-1;next[1]=0;
10
    for(int i=2,j=0;i<=len;i++){
11
        while(~j&&S[j+1]!=S[i])j=next[j];
12
        next[i]=++j;
13
    }
14
}
15
int main()
16
{
17
    while(1){
18
        memset(S,0,sizeof(S));
19
        scanf("%s",S);
20
        len=strlen(S)-1;
21
        if(S[0]=='.')break;
22
        get_next();
23
        //for(int i=1;i<=len;i++)printf("%d ",next[i]);
24
        //puts("");
25
        if((len+1)%(len-next[len])==0)printf("%d\n",(len+1)/(len-next[len]));
26
        else puts("1");
27
    }
28
}