【题目来源】：https://vjudge.net/problem/HDU-3746 【题意】 题意是给出一个字符串，要求变成一个周期串，最少需要几个字符？ 【思路】 也不知道怎地，想到了next数组，数组里记录的数字可以看成是一个周期。 举例说明： 字符串abcabcabc next数组：0 0 0 1 2 3 4 5 6 而字符串abcabc next数组：0 0 0 1 2 3 因为有大于0的数字的说明前面有重复的，并且，若是连续出现这样的会数字，说明一直连续，那不就是周期串了吗。。只需要字符总个数减去最后一位的next值，就可以得到最小循环周期，当然，可能会想这样的例子： abcabcabcaca 0 0 0 1 2 3 4 5 6 7 0 1 那么这个字符串的最小周期是几呢？ 答案是11。 【代码】
#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<limits.h> #include<algorithm> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int mod=1e9+7; const double esp=1e-5; typedef unsigned long long ll; typedef long long LL; char s[100000+10]; int ne[100000+10]; int n,maxx; void get_next() { int i=0,j; j=ne[0]=-1; while(i<n) { while(-1!=j&&s[i]!=s[j]) j=ne[j]; ne[++i]=++j; } } int main() { int T; scanf("%d%*c",&T); while(T--) { scanf("%s",s); n=strlen(s); get_next(); // for(int i=1;i<=n;i++) // { // cout<<ne[i]<<" "; // } // cout<<endl; int ans=n-ne[n]; // cout<<"ans="<<ans<<endl; if(ans==0) printf("0\n"); else if(ne[n]!=0&&n%ans==0) printf("0\n"); else printf("%d\n",ans-n%ans); } }