题意:
给出一个字符串,在所有长度大于1的前缀中,求所有的周期至少为2的周期串,并输出一个周期的长度以及周期的次数。
分析:
有了上一题 HDU 3746 的铺垫,这道题就很容易解决了
把next求出来,然后逐个判断即可。
#include <cstdio>
#include <cstring> const int maxn = + ;
char p[maxn];
int n, next[maxn]; void get_next()
{
int k = -, j = ;
next[] = -;
while(j < n)
{
if(k == - || p[k] == p[j])
{
k++;
j++;
next[j] = k;
}
else k = next[k];
}
} int main(void)
{
//freopen("1358in.txt", "r", stdin);
int kase = ;
while(scanf("%d", &n) == && n)
{
memset(next, , sizeof(next));
scanf("%s", p);
getchar();
get_next(); printf("Test case #%d\n", ++kase);
for(int i = ; i <= n; ++i)
{
if(next[i] == ) continue;
int cir = i - next[i];
if(i % cir == )
printf("%d %d\n", i, i / cir);
}
puts("");
} return ;
}
代码君