HDU_3746 Cyclic Nacklace 【KMP的应用】
一、题目
二、分析
KMP比较好解决的一个问题：如果求一个串中的循环节？
仔细回想KMP的用法，重点是next数组，相当于就是后缀和前缀的比较，那么不正是方便了我们确定循环节？
如果以字符串的最后一个位置（非字符）分析，那么这个位置的当前next值，就是我们串前缀和后缀的交集的最长值，所以只需要用长度Len去减去这个next值就可以得出循环节的长度了。
1 $Len\%(Len-next[Len]) && Len != Len - next[Len]$
此时，字符串已经满足循环的要求。
2 上面条件的反
此时，要求后面需要补多少字符串，答案就是$ (Len - next[Len]) - Len\%(Len-next[Len]) $ 其实就是循环节长度减去最后一未补齐的长度。
三、AC代码
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5 const int maxn = 1e5 + 14; 6 char s[maxn]; 7 int Next[maxn], Len; 8 9 void get_next() 10 { 11 Next[0] = -1; 12 int i = 0, j = -1; 13 while(i <= Len) 14 { 15 if(j == -1 || s[i] == s[j]) 16 { 17 i++; 18 j++; 19 Next[i] = j; 20 } 21 else 22 { 23 j = Next[j]; 24 } 25 } 26 } 27 28 int solve() 29 { 30 get_next(); 31 int ans = Len - Next[Len]; 32 if(Len % ans == 0 && Len != ans) 33 return 0; 34 else 35 return ans - (Len % ans); 36 } 37 38 int main() 39 { 40 //freopen("input.txt", "r", stdin); 41 int T; 42 scanf("%d", &T); 43 while(T--) 44 { 45 scanf("%s", s); 46 Len = strlen(s); 47 printf("%d ", solve()); 48 } 49 return 0; 50 }