首页 > 代码库 > HDU 2594 Simpsons’ Hidden Talents（KMP）
HDU 2594 Simpsons’ Hidden Talents（KMP）
【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=2594
【题目大意】
给出两个字符串，求第一个字符串和第二个字符串前缀和后缀的最大匹配。
【题解】
把s2串接在s1串的后面，那么这个串的前缀和后缀的最大匹配就是答案，注意在求nxt时候和失配指针和两个串长度比较的细节问题。
【代码】
#include <cstring>#include <cstdio>const int N=1000010; using namespace std;int nxt[N],i,k,j,t,n;char s[N];void get_nxt(int n,char*a){ int i,j; for(nxt[0]=j=-1,i=1;i<n;nxt[i++]=j){ while(~j&&a[j+1]!=a[i])j=nxt[j]; if(a[j+1]==a[i])j++; }}int main(){ while(~scanf("%s",s)){ int L1=strlen(s); scanf("%s",s+L1); int L=strlen(s),L2=L-L1; get_nxt(L,s); for(k=nxt[L-1];k>=L1||k>=L2;k=nxt[k]); if(k==-1)puts("0"); else{ for(int i=0;i<=k;i++)printf("%c",s[i]); printf(" %d\n",k+1); } }return 0;}
HDU 2594 Simpsons’ Hidden Talents（KMP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。