首页 > 代码库 > HDU 1358 Period (KMP)
HDU 1358 Period (KMP)
这道题对更加深入地理解next数组有很大帮助。
基本思路:
字符编号从0开始,那么if(i%(i-next[i])==0),则i前面的串为一个轮回串,其中轮回子串出现i/(i-next[i])次。
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1358
#include<stdio.h> int n,next[1000000]; char p[1000000]; void getnext() { int k=0,j=1; next[0]=-1;next[1]=0; while (j<n) { if (k==-1||p[j]==p[k]) { k++;j++; next[j]=k; } else k=next[k]; } } void kmp() { int i,t; for(i=2;i<=n;i++) { t=i-next[i]; if(i%t==0&&i/t>1) printf("%d %d\n",i,i/t); } } int main() { int i,num=0; while (scanf("%d",&n)&&n>0) { scanf("%s",p); printf("Test case #%d\n",++num); getnext(); kmp(); printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。