AcWing题目链接:https://www.acwing.com/problem/content/description/143/
HDU题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1358
子串的最小循环节就是x-Next[x],x是这个子串的长度,那么这道题我们就对字符串求一个Next数组,然后for循环扫一下每个前缀就好了。
AC代码:
#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
using namespace std;
int len;
char s[maxn];
int Next[maxn];
void init(){
int j = 0, k = -1;
memset(Next, -1, sizeof(Next));
while(j < len){
if(k == -1 || s[j] == s[k]){
k ++;
j ++;
Next[j] = k;
}
else k = Next[k];
}
}
int main()
{
int Case = 1;
while(~scanf("%d", &len)){
if(len == 0) break;
scanf("%s", s);
init();
printf("Test case #%d\n", Case ++);
for(int i=2;i<=len;i++){
int xx = i - Next[i];
if(i != xx && i % xx == 0){
printf("%d %d\n", i, i / xx);
}
}
puts("");
}
return 0;
}