hdu1358 Period KMP之next函数灵魂 KMP的周期 周期 周期

Period

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 964    Accepted Submission(s): 480

Problem DescriptionInputOutputSample InputSample Output#include<stdio.h>#include<string.h>int next[1000002],d;char a[1000002];void get_next(){int i=1,j=0;next[1]=0;while(i<=d){if(j==0||a[i]==a[j]) {i++;j++;next[i]=j;}else j=next[j];}}int main(){int i,k,t=0,flag;while(1){flag=1;memset(next,0,sizeof(next));scanf("%d",&d);if(d==0) return 0;scanf("%s",a+1);get_next();printf("Test case #%d\n",++t);// for(i=1;i<=d+1;i++) printf("%d ",next[i]);// printf("\n");for(i=2;i<=d;i++){k=i-(next[i+1]-1);/*next[i+1]-1是i+1之前的循环长度 用i一减就是剩下的长度 如果剩下的长度为一个重复串的长度则可以输出 否则不能输出 如 abcabcabc next[10]-1=6 用i一减（等于从abcabcabc中把abcabcabc拿走） 剩下个3（即abc） i是3的整数倍（长串的1到i的子串中是全由abc组成） 此时能输出next[9]-1=2 说明剩下的不够一个重复串 即不能被i整除 不能输出*/if(i!=k&&i%k==0) printf("%d %d\n",i,i/k);//i==k是指循环长度为0 即没有循环}printf("\n");}return 0;}/*非优化的next数组的含义是：next[i]=k模式串下标为i的字符的前k-1个字符与开首的前k-1个字符相等例如 aabaabaab next[10]=7 表示下标为10之前的字符前6个字符 与开首的前6个字符相等 所以当匹配不成功时 不用回溯到下标为6的位置去继续匹配*/