poj 1961 Period (KMP+最小循环节)
题目链接: poj 1961
题目大意: 给定字符串，找出他所有的前缀的最小循环节的长度
解题思路: 思路与2406一样
Tlen%(Tlen-next[Tlen])==0则Tlen-next[Tlen]是最小循环节
证明过程参考2406的解题报告
这里需要多次查询处理
代码:
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 1000010int 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;}elsej=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;}