POJ2406 Power Strings（KMP next）

题目链接

题意：求一个字符串中长度最短的循环节的循环次数。

KMP 中的 next 数组代表前缀与后缀相等的最长长度。

例如： a b a b a b

next:-1 0 0 1 2 3 4

next[n]==4,代表着，前缀与后缀相等的最长长度是 4（abab），若 l%(l-next[l]) == 0 则证明存在循环节。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
char a[1000005];
int nextt[1000005];

void kmp_pre(char x[],int m,int nextt[]){
    int i, j;
    j = nextt[0] = -1;
    i = 0;
    while(i < m){
        while(-1!=j && x[i]!=x[j])
            j = nextt[j];
        nextt[++i] = ++j;
    }
}


int main(){
    //freopen("a.txt", "r", stdin);
    while(~scanf("%s", a) && a[0] != '.'){
        int l = strlen(a);
        kmp_pre(a, l, nextt);
        if(l%(l-nextt[l]) == 0){
            int ans = l/(l-nextt[l]);
            cout << ans << endl;
        }

        else cout << "1" << endl;
    }
    return 0;
}