循环节问题
经典的利用kmp算法解决。
n-net[n]就是最小循环节cyc。
如果n%cyc==0那么我们可以说正好,不用加
否则就得加后缀
但是有一个需要判断的地方,当cyc==n的时候
没有循环节,那么我们要特殊判断了
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 1e5+100; int net[max_n]; void getnext(char p[],int size) { int i = 0;int j = -1; net[0] = -1;net[size]=500;//绝对不会出现的数 while (i < size) { if (j == -1 || p[i] == p[j]) { ++i;++j; if (p[i] != p[j]) net[i] = j; else net[i] = net[j]; } else j = net[j]; } } char p[max_n]; int main(){ int T;scanf("%d",&T); while (T--){ scanf("%s",p); int n=strlen(p); getnext(p,n); int cyc = n-net[n]; if (cyc==n)printf("%d\n",n); else if (n%cyc==0)printf("0\n"); else printf("%d\n",cyc-n%cyc); } }