HDU 1358 (所有前缀中的周期串) Period

时间:2021-01-07 03:50:48

题意:

给出一个字符串,在所有长度大于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 ;
}

代码君