HDU 3746 Cyclic Nacklace(KMP求最小循环元)
/*题意：组成一个环，要求至少包含两个相同字符串，求至少向给出字符串后面添加的字符数题解：根据KMP求出循环元，最小循环元t = len - next[len]。然后问题就很容易解决了。做完这道题，感触更深一些了，这个公式对任何字符串都适用。*/#include <iostream>using namespace std;const int nMax = 100010;int T;char s[nMax];int next[nMax];void getNext(char *s, int *next, int len){int i, j;i = 0, j = -1;//j需要从-1开始，需要跟前一位比较next[0] = -1;while(i < len){if(j == -1 || s[i] == s[j]){i ++;j ++;next[i] = j;}elsej = next[j];}}int main(){//freopen("e://data.in", "r", stdin);scanf("%d", &T);while(T --){scanf("%s", s);int len = strlen(s);getNext(s, next, len);int t = len - next[len];//KMP求出循环元，len - next[len]即为循环元if(len % t == 0){if(len == t) printf("%d\n", len);else printf("0\n");}else{t =t - len % t;printf("%d\n", t);}}}