题目链接
讲解引用博客
循环节部分有待继续理解
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
char s[maxn];
int f[maxn];void solve()
{int m = strlen(s);f[0] = f[1] = 0;for(int i = 1; i < m; i++){int j = f[i];while(j && s[i] != s[j]) j = f[j];f[i + 1] = s[i] == s[j] ? j + 1 : 0; //例如：abcdabe,e失配的话会回溯到c,因为有公共前缀ab}
}int main()
{cin >> s;solve();for(int i = 0; i < strlen(s); i++)cout << i << " " << f[i] << endl;int n = strlen(s);/*for(int i = 0; i <= n; i++)cout << f[i] << " ";cout << endl;*/for(int i = 2; i <= n; i++){if(f[i] > 0 && i % (i - f[i]) == 0) printf("%d %d\n", i, i / (i - f[i]));//if(f[i] > 0 && (f[i] + 1) % (i - f[i]) == 0)//printf("%d %d\n", i + 1, (f[i] + 1) / (i - f[i]) + 1); 个人理解也可以}return 0;
}