首页 > 代码库 > hdu1358 KMP求字符串最小循环节
hdu1358 KMP求字符串最小循环节
对于一个字符串S，长度为L，如果由长度为len的字符串s（字符串s的最小循环节是其本身）循环k次构成，那么字符串s就是字符串S的最小循环节
那么字符串有个很重要的性质和KMP挂钩，即 i - next[i] 为字符串s的长度 i%（i - next[i]) ==0
证明：字符串S由s循环k次构成，那么有S[0-->L-len-1] == S[len-->L-1],即前k-1个循环节和后k-1个循环节构成的字符串相等
那么此时KMP数组的next[L] = k-1个循环节的长度， 也即 next[L] = L-len-1+1 = L - len,那么此时 L - next[L] = len , 所以 L % len = 0, L % len = k
所以如果字符串存在循环节，那么i % (i - next[i]) ==0，循环节的长度为 i % ( i - next[i])
否则，循环节的为字符串本身。
1 #include <stdio.h> 2 #include <string.h> 3 const int N = 1000000 + 10; 4 char str[N]; 5 int next[N]; 6 void makeNext(char *str) 7 { 8 int i=0,j=-1; 9 next[0] = -1;10 while(str[i])11 {12 if(j==-1||str[i]==str[j])13 {14 i++;15 j++;16 next[i] = j;17 }18 else19 j = next[j];20 }21 }22 int main()23 {24 25 int n;26 int tCase = 1;27 while(true)28 {29 scanf("%d",&n);30 if(n==0)31 break;32 scanf("%s",str);33 makeNext(str);34 printf("Test case #%d\n",tCase++);35 for(int i=2; i<=n; ++i)36 {37 if(i%(i-next[i])==0 && next[i]!=0)//next[i]!=0,如果为0，循环节是本身38 printf("%d %d\n",i,i/(i-next[i]));39 40 }41 puts("");42 43 }44 return 0;45 }
hdu1358 KMP求字符串最小循环节
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。