HDU 3746 KMP_Next 找循环节
题意：给你一个字符串，使添加最少的字符，使得这个字符串由一个循环节循环2次构成。
思路：这道题和POJ 1961差不多，POJ 1961:http://blog.csdn.net/just_water/article/details/12169609
也是找循环节，那么根据POJ 1961的结论，我们很容易推出，当字符串长度为l时，如果next[l] = k ,并且l % (l - k) == 0，那么已经存在循环节，该循环节的长度为(l - k)。
如果不等于0，那么还需要(l - k) - l % (l - k) 这么多的字符，才能使得这个字符串成为循环节为(l - k )的循环串。
#include <set>#include <map>#include <stack>#include <cmath>#include <queue>#include <cstdio>#include <string>#include <vector>#include <iomanip>#include <cstring>#include <iostream>#include <algorithm>#define Max 2505#define FI first#define SE second#define ll long long#define PI acos(-1.0)#define inf 0x3fffffff#define LL(x) ( x << 1 )#define bug puts("here")#define PII pair<int,int>#define RR(x) ( x << 1 | 1 )#define mp(a,b) make_pair(a,b)#define mem(a,b) memset(a,b,sizeof(a))#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )using namespace std;#define N 222222int Next[N] ;char a[N] ;void get_Next(){ Next[0] = -1 ; int k = -1 , j = 0 ; int l = strlen(a) ; while(j < l && k < l){ if(k == -1 || a[k] == a[j]){ k ++ ; j ++ ; Next[j] = k ; } else k = Next[k] ; }}void solve(){ scanf("%s",a) ; get_Next() ;int l = strlen(a) ; int k = Next[l] ; int d = l - k ;//循环节 if(k == 0)printf("%d\n",l) ; else { if(l % d == 0)cout << 0 << endl ;//已经是一个循环节了 else cout << d - l % d << endl ;//还需要d - l % d 个字符才能成为循环节 }}int main() { int _ ; cin >> _ ; while(_ -- )solve() ; return 0 ;}