最小循环节问题
#include<cstdio> #include<cstring> using namespace std; const int max_n = 1e6 + 100; char s[max_n]; int net[max_n]; int n; void get_next(char* p) { net[0]=-1; for (int i = 0, j = -1;i < n;) { if (j == -1 || p[i] == p[j])net[++i] = ++j; else j = net[j]; } } int main() { while (scanf("%s",s)) { if (s[0] == '.')break; n = strlen(s); get_next(s); int len = n - net[n]; if (n % len == 0)printf("%d\n",n/len); else printf("1\n"); } }