两道题类似，uva455是求最小周期，hdu3746是求最少插入多少字符可以使得字符串最少有两个周期。
类似于kmp算法，使用一个next数组， 对字符串进行处理，标记所有的前缀， 时间复杂度是O(n)。
如：
字符串： a b c a b c d a b e f
next数组： 0 0 0 1 2 3 0 1 2 0 0
然后通过next数组来判断周期。
uva455 Periodic Strings：
#include <iostream> #include <cstring> using namespace std; void get_next(char P[], int next[], int m) { next[0] = 0; for (int i = 1, k = 0; i < m; ++i) { while (k > 0 && P[i] != P[k]) k = next[k - 1]; if (P[i] == P[k]) ++k; next[i] = k; } } int main() { int T, next[105]; char s[105]; cin >> T; while (T--) { cin >> s; int len = strlen(s); get_next(s, next, len); int ans, k = len - next[len - 1]; if (len % k == 0) ans = k; else ans = len; cout << ans << endl; if (T) cout << endl; } return 0; } hdu3746 Cyclic Nacklace:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; void get_next(char P[], int next[], int n) //求next数组 { next[0] = 0; for (int i = 1, k = 0; i < n; ++i) { while (k > 0 && P[i] != P[k]) k = next[k - 1]; if (P[i] == P[k]) ++k; next[i] = k; } } int main() { int T, next[100005]; char s[100005]; scanf("%d", &T); while (T--) { scanf("%s", s); int n = strlen(s); get_next(s, next, n); int ans, k = n - next[n - 1]; if (k == n) // k==n时， next[n - 1]为0，所以需要插入n个字符 ans = n; else if (n % k == 0) //此时，字符串中已经至少两个周期 ans = 0; else ans = k - n % k; printf("%d\n", ans); } return 0; }
