HDU3746 Cyclic Nacklace

题目链接：https://vjudge.net/problem/HDU-3746

知识点：　　KMP

解题思路：

　　论如何用 (Next[]) 数组求循环节。

AC代码：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int maxn = 100000+5;
 5 char inp[maxn];
 6 int Next[maxn];
 7 void init(int plen){
 8     memset(Next,0,sizeof(Next));
 9     int i=0,j=-1;
10     Next[0]=-1;
11     while(i<plen){
12         if(j==-1||inp[i]==inp[j]){
13             i++,j++;
14             Next[i]=j;
15         }
16         else
17             j=Next[j];
18     }
19 }
20 int main(){
21     int T;
22     scanf("%d",&T);
23     while(T--){
24         scanf("%s",inp);
25         int len=strlen(inp);
26         init(len);
27         int tmp=len-Next[len];  //tmp:循环节长度
28         if(tmp!=len&&len%tmp==0)    printf("0
");
29         else    printf("%d
",tmp-Next[len]%tmp);   //%tmp有效地忽略了Next[len]里面的完整的循环节
30     }
31     return 0;
32 }

“这些年我一直提醒自己一件事情，千万不要自己感动自己。大部分人看似的努力，不过是愚蠢导致的。什么熬夜看书到天亮，连续几天只睡几小时，多久没放假了，如果这些东西也值得夸耀，那么富士康流水线上任何一个人都比你努力多了。人难免天生有自怜的情绪，唯有时刻保持清醒，才能看清真正的价值在哪里。”