E : 子串循环问题 (Ver. I)

E : 子串循环问题 (Ver. I)

Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 18     Solved: 12

Description

给定一个字符串，求需要添加至少几个字符到字符串末尾才能使得整个字符串由某一个不为本身的子串循环构成？ 如“abca”，添加“bc”后构成“abcabc”，其由子串“abc”循环构成;也可以添加“abca”后构成“abcaabca”，其由子串“abca”循环构成，相比之下“bc”只有2个字符，添加的字符量最少。

Input

第一行包括一个整数T(1 <= T <= 100)，代表测试组数

每组测试数据包括一行字符串，其长度范围为 [3, 10^4]

Output

对于每组测试数据

输出一个整数N，代表添加的最小字符数量

Sample Input

4
aaa
abca
abcdefg
abcabcabca

Sample Output

0
2
7
2

ac代码如下：
大致思路是：利用KMP算法中的其中一个核心函数Get_next（string a）来算next[a.size()]多少，然后分重叠串和非重叠串进行分类计算

#include<iostream>
using namespace std;

int Get_next(string a)
{
    int len=a.size();
    int i=0,k=-1;
    int *next=new int[len+1];
    next[0]=-1;
    while(i<len)
    {
        if(k==-1||a[i]==a[k])
        {
            i++,k++;
            next[i]=k;
        }
        else k=next[k];
    }
    if(next[len]*2>=len)
    {
        if(len%(len-next[len])==0)return 0;
        else return (len-next[len])-len%(len-next[len]);
    }
    else return len-next[len]*2;

}
int main()
{
    string a;
    int n;
    cin>>n;
    while(n--)
    {
        cin>>a;
        cout<<Get_next(a)<<endl;
    }
    return 0;
}