这题琢磨了挺长的时间。需要理解next[]表示了什么; next[i]代表了前缀和后缀的最大匹配的值，也就是个数。
len-next[len]表示循环节的长度; 比如abcab int fl=len-next[len]=3;循环节长度为3,即cab。然后int len=strlen(s)=5；
如果len%fl==0,那就count=len/fl,不然count=len/fl+1;count表示根据长度能够循环的次数。count*fl表示能够满足循环的时候的长度，
count*fl-len就是缺少的长度。不过如果next[len]==0，也就是本身的时候，就要输出自己的len了；
#include<stdio.h> #include<string.h> #define maxn 100010 char c[maxn]; int next[maxn]; void getnext() { int j,k,len=strlen(c); j=0; k=-1; next[0]=-1; while(j<len) { if(k==-1||c[j]==c[k]) { j++; k++; next[j]=k; } else k=next[k]; } } void kmp() { int i,j; getnext(); int len=strlen(c); /*for(i=0;i<=len;i++) printf("%d ",next[i]); printf("\n");*/ int fl=len-next[len];//循环节长度 int count=0; i=len; count=len/fl;//循环节的次数 if(len%fl)//如果不能整除就要+1 count++; // printf("%d %d ",fl,count); if(next[len]==0)//如果直接为0 所以就本身长度 printf("%d\n",len); else printf("%d\n",count*fl-len); } int main() { int i,j,t; scanf("%d",&t); while(t--) { scanf("%s",c); kmp(); } }
原文：http://www.cnblogs.com/sweat123/p/4721074.html