POJ 2406 Power Strings kmp

Description

Input

Output

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

Hint

Source

Waterloo local 2002.07.01

AC code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define maxn 1000005
using namespace std;
int next[maxn];
int main(){
    char s[maxn];
    while(scanf("%s",s)!=EOF&&strcmp(s,".")){
        int k=0,len=strlen(s),i,j;
        j=0,k=-1;
        next[0]=-1;
        while(j<len){
            if(k==-1||s[j]==s[k]){
			j++;k++;
			if(s[j]!=s[k])next[j]=k;
            else next[j]=next[k];
            }
            else k=next[k];
        }
        if(len%(len-next[len])==0)
            cout<<(len/(len-next[len]))<<'\12';
        else printf("1\n");
    }
    return 0;
}

POJ 2406 Power Strings kmp

原文：http://blog.csdn.net/zp___waj/article/details/47680537