题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1358
题意 :求给你个串,前i位子串由某个字符串重复k次得到,求所有的i和k(k>1);
例如:
aabaabaabaab
前2个字符由2个a构成;
前6个字符由2个aab构成;
前9个字符由3个aab构成;
前12个字符由4个aab构成;
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std; const int N = 1e6+; char s[N];
int Next[N], n; void GetNext()
{
int i=, j=-;
Next[] = -;
while(i<n)
{
if(j==- || s[i] == s[j])
Next[++i] = ++j;
else
j=Next[j];
}
}
int main()
{
int t=;
while(scanf("%d", &n),n)
{
scanf("%s", s);
GetNext();
printf("Test case #%d\n", t++);
for(int i=; i<=n; i++)
{
int Min_cycle = i - Next[i];
if(i%Min_cycle== && i/Min_cycle != )///题中说了循环k次, k > 1的
printf("%d %d\n", i, i/Min_cycle);
}
printf("\n");
}
return ;
}