题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1358
题目描述：
给出一个字符串S，输出S的前缀能表达成Ak的所有情况，每种情况输出前缀的结束位置和k。
解题思路：
打表算出next数组，然后对位置i求循环节，如果满足 i % (i - Next[i]) == 0 && Next[i] != 0，所对应的循环节(i - Next[i]), 循环次数是i / (i - Next[i])
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std; #define LL long long
#define maxn 1000010
#define mod 100000007 char a[maxn];
int Next[maxn], m; void get_next (char a[])
{
int i, j;
Next[] = j = -;
i = ; while (i < m)
{
while (j!=- && a[i]!=a[j])
j = Next[j]; Next[++ i] = ++j;
}
} void solve ()
{
for (int i=; i<=m; i++)
{
if (Next[i] != && i % (i - Next[i]) == )
printf ("%d %d\n", i, i / (i - Next[i]));
}
printf ("\n");
}
int main ()
{
int l = ;
while (scanf ("%d", &m), m)
{
scanf ("%s", a);
get_next (a); printf ("Test case #%d\n", ++l); solve ();
}
return ;
}
/*
3
aabccb
*/