hdu 3746 Cyclic Nacklace

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3746

思路：KMP中Next数组的应用，求出最小的循环节，题目的意思是只能在字符串的后面上添加新的字符凑成两个循环节

用Next数组来求最小循环节的方法见这：http://www.cnblogs.com/wuyiqi/archive/2012/01/06/2314078.html

1 #include<string.h> 2 #include<stdio.h> 3 #include<iostream> 4 #define N 1000005 5 6 using namespace std; 7 8 int Next[N],tlen; 9 char T[N]; 10 11 void getNext() 12 { 13 int j, k; 14 j = 0; k = -1; Next[0] = -1; 15 while(j < tlen) 16 { 17 if(k == -1 || T[j] == T[k]) 18 Next[++j] = ++k; 19 else 20 k = Next[k]; 21 } 22 } 23 24 int main() 25 { 26 int cas,min; 27 scanf("%d",&cas); 28 while(cas--) 29 { 30 scanf("%s",T); 31 tlen=strlen(T); 32 getNext(); 33 min=tlen-Next[tlen]; 34 if(min==tlen) 35 printf("%d\n",tlen); 36 else if(tlen%min==0) 37 printf("0\n"); 38 else 39 printf("%d\n",min-tlen%min); 40 } 41 return 0; 42 }

 

转载于:https://www.cnblogs.com/pter/p/5717652.html

总结

以上是生活随笔为你收集整理的hdu 3746 Cyclic Nacklace的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。