循环节问题

其实和上一题差不多。
关键都是如何判断循环节罢了

我们求出next数组后,取遍历索引
求出当前数组的循环节i-next[i]
然后如果cyc==i就没有循环节
如果i%cyc!=0就不是完整循环节

然后输出就好了

#include<iostream>
#include<algorithm>
using namespace std;
const int max_n = 1e6+100;
int n;
int net[max_n];
char p[max_n];

void getnext(){
    net[0]=-1;net[n]=500;
    for (int i=0,j=-1;i<n;){
        if (j==-1||p[i]==p[j])net[++i]=++j;
        else j=net[j];
    }
}


int main(){
    int tcase = 0;
    while(scanf("%d",&n)&&n){
        printf("Test case #%d\n",++tcase);
        scanf("%s",p);
        getnext();
        for (int i=1;i<=n;++i){
            int cyc = i-net[i];
            if (cyc==i)continue;
            else if (i%cyc==0)printf("%d %d\n",i,i/cyc);
        }puts("");
    }
}