Period HDU - 1358 kmp求循环节

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int n;
char a[maxn];
int ne[maxn];
void cal_next(char b[]) {
    for (int i=2,j=0;i<=n; i++) {
        while(j&& b[j+1]!=b[i])
            j=ne[j];
        if(b[j+1]==b[i])
            j++;
        ne[i]=j;
    }
}
int main() {
    int cnt = 0;
    while (~scanf("%d", &n)) {
        if (n == 0)
            break;
        scanf("%s", a+1);
        printf("Test case #%d\n", ++cnt);
        cal_next(a);
        for (int i=1;i<=n;i++) 
        {
            if(ne[i]==0)
                continue;
            //表示往前跳了多少，也就是循环节的长度 
            int len=i-ne[i];
            //如果是循环节 ， 
            if(i%len==0) 
                                //循环次数 
                printf("%d %d\n",i,i/len);
        }
        printf("\n");
    }
    return 0;
}

Period HDU - 1358 kmp求循环节

原文：https://www.cnblogs.com/QingyuYYYYY/p/12384396.html