题意

给你个字符串,问在字符串末尾还要添加几个字符，使得字符串循环2次以上。

解法

无论这个串是不是循环串

i-next[i] 都能求出它的最小循环节

代码：

/*

思路：kmp+字符串的最小循环节问题

分析：

1 题目要求的是给定一个字符串，问我们还需要添加几个字符可以构成一个由n个循环节组成的字符串。

2 可知我们应该先求出字符串的最小循环节的长度：假设字符串的长度为len，那么最小的循环节就是cir = len-next[len] ;

如果有len%cir == 0,那么这个字符串就是已经是完美的字符串，不用添加任何字符；

如果不是完美的那么需要添加的字符数就是cir - (len-(len/cir)*cir))，相当与需要在最后一个循环节上面添加几个。

3 如果cir = 1，说明字符串只有一种字符例如“aaa” ;

 如果cir = m说明最小的循环节长度为m，那么至少还需m个；

 如果m%cir == 0，说明已经不用添加了。

*/

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

char str[100005];

int next[100005];

void getnext(int len)

{

    int i = 0,j = -1;

    next[0] = -1;

    while(i<len)

    {

        if(j == -1 || str[i] == str[j])

        {

            i++;

            j++;

            next[i] = j;

        }

        else

            j = next[j];

    }

}

int main()

{

    int n;

    cin >> n;

    getchar();

    while(n--)

    {

        gets(str);

        memset(next,0,sizeof(next));

        int len = strlen(str);

        int ans;

        getnext(len);

        ans = len - next[len];

        if(ans!=len && len%ans == 0)

        cout << 0 << endl;

        else

        cout << ans-next[len]%ans << endl;

    }

    return 0;

}