首页 > 代码库 > HDU 2594 Simpsons’ Hidden Talents (KMP)
HDU 2594 Simpsons’ Hidden Talents (KMP)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2594
这题直接用KMP算法就可以做出来,不过我还尝试了用扩展的kmp,这题用扩展的KMP效率没那么高。
KMP算法:
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; int next[50001]; char p[50000],s[50000]; void getnext() { int plen=strlen(p),k=0,j=1; next[0]=-1;next[1]=0; while (j<plen) { if (k==-1||p[j]==p[k]) { k++;j++; next[j]=k; } else k=next[k]; } } int kmp() { int i=0,j=0,slen=strlen(s),plen=strlen(p); while (i<slen) { if (j == -1 || s[i] == p[j]) { i++; j++; } else j=next[j]; } if (j==-1) j=0; return j; } int main() { int i; while (scanf("%s%s",p,s)!=EOF) { getnext(); i=kmp(); if (i) { for (int j=0;j<i;j++) printf("%c",p[j]); printf(" %d\n",i); } else printf("0\n"); } return 0; }
扩展的KMP:
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; char S[50000],T[50000]; int A[50001],B[50001],sl,tl; void getA() { int j=0; while(1+j<tl&&T[0+j]==T[1+j]) j++; A[1]=j; int k=1; for(int i=2;i<tl;i++) { int len=k+A[k]-1,l=A[i-k]; if(l<len-i+1) A[i]=l; else { j=max(0,len-i+1); while(i+j<tl&&T[i+j]==T[0+j]) j=j+1; A[i]=j;k=i; } } } void getB() { getA(); int j=0; while(j<sl&&j<tl&&T[0+j]==S[0+j]) j++;B[0]=j; int k=0; for(int i=1;i<sl;i++) { int len=k+B[k]-1,l=A[i-k]; if(l<len-i+1) B[i]=l; else { j=max(0,len-i+1); while(i+j<sl&&j<tl&&S[i+j]==T[0+j]) j=j+1; B[i]=j,k=i; } } } int main() { int i; while (~scanf ("%s %s",T,S)) { int num=0; sl=strlen(S),tl=strlen(T); getB(); for (i=0;i<sl;i++) if (B[i]==sl-i) { num=B[i]; break; } if (num>0) { for (int j=0;j<num;j++) printf("%c",T[j]); printf(" "); } printf("%d\n",num); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。