循环节问题
其实和上一题差不多。
关键都是如何判断循环节罢了
我们求出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(""); } }