既然要循环的话,那么肯定前缀和后缀要相等,所以先求next数组,而想要知道有多少个循环,那么比如ababab,Next[len] = 4,也就是说前缀abab = 后缀abab,则前缀中的重合的ab = 后缀中的后面的ab而后缀中重合的ab等于前缀中的前面的ab,所以就可以知道循环节为len / (len - Next[len])(整除的情况),否则为1。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 1e+6 + 10; int Next[maxn]; char mo[maxn]; void GetNext() { int i = 0, j = -1, len = strlen(mo); while (i < len) { if (j == -1 || mo[i] == mo[j]) Next[++i] = ++j; else j = Next[j]; } } int main() { ios::sync_with_stdio(false); while (scanf("%s", mo) != EOF && mo[0] != '.') { Next[0] = -1; GetNext(); int len = strlen(mo), Max = 0; if (len % (len - Next[len]) == 0) printf("%d\n", len / (len - Next[len])); else printf("1\n"); } return 0; }