poj 1961 Period (KMP+最小循环节)
题目大意: 给定字符串，找出他所有的前缀的最小循环节的长度解题思路: 思路与2406一样
Tlen%(Tlen-next[Tlen])==0则Tlen-next[Tlen]是最小循环节
证明过程参考2406的解题报告
这里需要多次查询处理
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000010
int next[MAX],Tlen;
char ch[MAX];
void Get_next()
{
int i=0,j=-1;
next[0]=-1;
while(i<Tlen)
{
if(j==-1||ch[i]==ch[j])
{
i++; j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
int n,i=1,j;
while(scanf("%d",&Tlen)!=EOF&&Tlen)
{
memset(next,0,sizeof(next));
scanf("%s",ch);
Get_next();
printf("Test case #%d\n",i++);
for(j=1;j<Tlen;j++)
{
n=j+1-next[j+1];
if((j+1)%n==0&&(j+1)!=n) //***
printf("%d %d\n",j+1,(j+1)/n); //***
}
puts("");
}
return 0;
}
补充：软件开发 , C++ ,
