题解：

题目大意：有一个字符串s。能够在前后加入字符，使字符串成为一个循环次数至少为2的循环字符串。输出最少须要加入的字符数目。

首先能够证明题目能够等价为仅仅在末尾加入字符使满足题意。要找到加入资格字符我们首先要找到循环单位的长度。利用一个辅助数组储存从起始位置開始长度为i的串的循环长度，初始值为i，利用与Next数组之间的关系来更新。找到循环长度。比方字符串abcabc,Next[i] = 3,cycle[3] = 3,有等价关系i-Next[i] = cycle[Next[i]];所以循环长度为3.可是注意假设某个字符不能与上一个字符串相应。则须要更新循环长度为当前字符串长度。

例子：

abcdabcda

3

ababac

6

aaaaab

6

代码实现：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define MAX 100010using namespace std;int T;int res;int len;char s[MAX];int Next[MAX];int cycle[MAX];void getnext();int main(){    scanf("%d",&T);    getchar();    while( T-- ){        gets(s);        len = strlen(s);        getnext();        res = len;        for( int i = 1; i <= len; i++ ){            cycle[i] = i;            int tmp = Next[i];            if( cycle[tmp] == i-tmp ){                cycle[i] = cycle[tmp];                res = cycle[i];            }            else if( res != len && s[i-1] != s[i-res-1] ){                res = cycle[i];            }        }        if( len == res ){            res = len-Next[len]*2;        }        else if( len%res == 0 ){            res = 0;        }        else{            res = res-(len%res);        }        printf("%d\n",res);    }    return 0;}void getnext(){    memset(Next,0,sizeof(Next));    Next[0] = -1;    int i = 0, j = -1;    while( i < len ){        if( j == -1 || s[i] == s[j] ){            Next[++i] = ++j;        }        else{            j = Next[j];        }    }    return ;}
         
        
       
      

另外看到同学的一种递归写法。感觉更巧妙一点，理解起来不太easy。

核心代码：

int solve(int pos){    int tmp = Next[pos]*2;    //无重叠    if( tmp <= pos ){        return pos-tmp;    }    //有重叠    else{        return solve(Next[pos]);    }}

理解：

对于一个字符串来说，他的前缀串与后缀串分为有重叠和无重叠两种情况。

比方abcabcabc是有重叠；abcab是无重叠，详细关系体如今2*Next与pos大小比較。无重叠我们能够直接输出前缀串与后缀串不同样的部分；对于有重叠我们要递归的向前去找，找到缺少的部分的长度。比方我们用AXBYC表示一个重叠串，当中每一个大写字母表示一个子串，而B为重叠部分，能够证明的是A=B=C,X=Y,作为循环单位缺少的一部分我们要向前递归，知道子串的前缀串与后缀串不再重叠，从而找到X的长度，而特殊情况aaaaaaaaaa。依照上面的定义则他的ABC都是重叠的。所以递归找子问题，直到不再重叠。