KMP算法——
AC代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int N=200005; const LL II=100000000; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); int next[N],len,nextval[N]; char str[N]; void getnext(char *p) { int j=0,k=-1; next[0]=-1; while(j>T; while(T--) { scanf("%s",str); len=strlen(str); getnext(str); int min_repeat=len-next[len]; if(min_repeat==len) printf("%d\n",len); else if(len%min_repeat==0) printf("0\n"); else printf("%d\n",min_repeat-len%min_repeat); } return 0; } #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int N=200005; const LL II=100000000; const int INF=0x3f3f3f3f; const double PI=acos(-1.0); int next[N],len,nextval[N]; char str[N]; void getnext(char *p) { int j=0,k=-1; next[0]=-1; while(j>T; while(T--) { scanf("%s",str); len=strlen(str); getnext(str); int min_repeat=len-next[len]; if(min_repeat==len) printf("%d\n",len); else if(len%min_repeat==0) printf("0\n"); else printf("%d\n",min_repeat-len%min_repeat); } return 0; }