POJ1961 Period（KMP next）

题目链接

POJ2406的加强版，2406 是求一个字符串中循环节次数，而这道题是输出所有前 i 个字符构成的字符串的循环节次数，所以在求 next 数组中，每求出一次就判断一次是否有循环节，如果有就输出。

#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], l;

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;
        if(nextt[i]!=0 && i%(i-nextt[i]) == 0){
            int ans = i/(i-nextt[i]);
            cout << i << " " << ans << endl;
        }
    }
}


int main(){
    //freopen("a.txt", "r", stdin);
    int n, cas = 1;
    while(~scanf("%d", &n) && n){
        scanf("%s", a);
        printf("Test case #%d\n", cas++);
        kmp_pre(a, n, nextt);
        cout << endl;
    }
    return 0;
}