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

题意：

最少还要加多少珠子能使手链变成循环手链。

思路：

这题和HDU的1358题类似，求出字符串的最小循环节即可。

My  Code：

#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
char ch[100005];
int nt[100005];
int len;
void GetNext()
{
    int j = 0,k = -1;
    nt[0] = -1;
    while(j < len)
    {
        if(k == -1 || ch[j]== ch[k])
        {
            j++; k++;
            nt[j] = k;
        }
        else k = nt[k];
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",ch);
        len = strlen(ch);
        GetNext();
        if(nt[len] == 0)
            printf("%d\n",len);
        else
        {
            int ans = len - nt[len];///ans记录的是最小循环子序列的长度
            if(len % ans == 0)///如果除不尽的话（即有余数）说明不是一个手链，如果len%ans=0的话，则说明此串是由k个最小循环子序列组成的，即此串本身就是一个手链
                printf("0\n");
            else
                printf("%d\n",ans - len % ans );///用最小循环子序列-最小前后缀就是要增加的序列长度（其中len%ans算出来的是最小循环子序列中已有的一部分）
        }
    }
}