POJ 2406 Power Strings 题解 KMP 适配函数

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

abcd
aaaa
ababab
.

Sample Output

1
4
3

题解

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

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000005;
char S[N];
int next[N],len;
void get_next(){
    next[0]=-1;next[1]=0;
    for(int i=2,j=0;i<=len;i++){
        while(~j&&S[j+1]!=S[i])j=next[j];
        next[i]=++j;
    }
}
int main()
{
    while(1){
        memset(S,0,sizeof(S));
        scanf("%s",S);
        len=strlen(S)-1;
        if(S[0]=='.')break;
        get_next();
        //for(int i=1;i<=len;i++)printf("%d ",next[i]);
        //puts("");
        if((len+1)%(len-next[len])==0)printf("%d\n",(len+1)/(len-next[len]));
        else puts("1");
    }
}