传送门：点击打开链接
题意：给一个字符串s，求所有的前缀中是否能能通过一段循环得到，如果能，输出位置和循环的次数，循环次数越小越好。
思路：先通过KMP求出Next数组(我的Next数组的写法，是Next[0]=0,这个看个人习惯
之后直接判断Next[i] && (i + 1) % (i - Next[i] + 1) == 0就能知道是否可以搞定了
详细证明可以去看训练指南，上面讲的很详细。
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout << "[" << x << "]"
#define FIN freopen("input.txt", "r", stdin)
#define FOUT freopen("output.txt", "w+", stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 2e6 + 5;char S[MX];
int Next[MX], n;
void GetNext() {Next[0] = 0;for(int i = 1; i < n; i++) {int j = Next[i - 1];while(j && S[i] != S[j]) j = Next[j - 1];Next[i] = S[i] == S[j] ? j + 1 : 0;}
}int main() {int ansk = 0; //FIN;while(~scanf("%d", &n), n) {scanf("%s", S);GetNext();printf("Test case #%d\n", ++ansk);for(int i = 1; i < n; i++) {if(Next[i] && (i + 1) % (i - Next[i] + 1) == 0) {printf("%d %d\n", i + 1, (i + 1) / (i - Next[i] + 1));}}printf("\n");}return 0;
}