首页 > 代码库 > hdu 3746 Cyclic Nacklace

hdu 3746 Cyclic Nacklace

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

题目大意:补充珠子数使其成为手链,手链的规格是:比如这一组数据:abca,要想成为手链,必须满足abcabc,还要加两个,所以输出2。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 char str[1000005]; 6 int next[100005],len; 7  8 void get_next() 9 {10     int i=0,j=-1;11     next[0]=-1;12     len=strlen(str);13     while (i<len)14     {15         if (j==-1||str[i]==str[j])16         {17             i++;18             j++;19             next[i]=j;20         }21         else22             j=next[j];23     }24 }25 26 int main ()27 {28     int t;29     scanf ("%d",&t);30     while (t--)31     {32         scanf("%s",str);33         get_next();34         //for (int i=0;i<len;i++)35         //cout<<next[i]<<endl;  36         int q=len-next[len];37         if (len%q==0&&len!=q)38             printf ("0\n");39         else40             printf("%d\n",q-len%q);41     }42     return 0;43 }