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
",tlen);
36         else if(tlen%min==0)
37             printf("0
");
38         else
39             printf("%d
",min-tlen%min); 
40     }
41     return 0;
42 }