Sample Input
3
aaa
abca
abcde
Sample Output
0
2
5
给你一些串,问如果想让这个串里面的循环节至少循环两次,需要添加几个字符(只能在最前面或者最后面添加)。比如ababc 需要添加5个就是添加ababc。
利用Next数组的性质:
符合 i % ( i - next[i] ) == 0 && next[i] != 0 , 则****说明字符串循环,而且
循环节长度为: i - next[i]
循环次数为: i / ( i - next[i] )
#include <stdio.h> #include <string.h> const int N = 1e5+5; int n, next[N]; char str[N]; void getNext () { n = strlen (str+1); int p = 0; for (int i = 2; i <= n; i++) { while (p > 0 && str[p+1] != str[i]) p = next[p]; if (str[p+1] == str[i]) p++; next[i] = p; } } int main () { int cas; scanf("%d", &cas); while (cas--) { scanf("%s", str+1); getNext(); int n= strlen (str+1); if (next[n] == 0) printf("%d\n", n); else { int k = n - next[n]; if (n%k == 0) printf("0\n"); else printf("%d\n", k - (n - (n/k) * k)); } } return 0; }