算法题：HDU 2594 Simpsons’ Hidden Talents(KMP）

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2594

题目大意：

给两个字符串s1和s2, 求出是s1的前缀并且是s2的后缀的最长的字符串。

分析与总结：

真正理解好KMP算法，这题就是水题。

首先求出s1的失配函数，然后在s2中 寻找s1字符串。

在寻找字符串过程中，会有一个状态值j，这个值表示的是当前在s2中已经匹配 了多少个s1的字符。 所以，全部匹配完后，最后j的值就是以s2的最后一个字符结尾，和s1的前缀相匹 配的最长字符串。也就是所求的答案了。

还有一种方法：

网上有不少题解貌似都是把s1 和s2拼接起来成s3，然后求s3自身的next，原理其实是一样的。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;  

const int MAXN = 50005;
char s1[MAXN];
char s2[MAXN];
int  f[MAXN];  

void getFail(char *p, int *f){
    int n=strlen(p);
    f[0]=f[1]=0;
    for(int i=1; i<n; ++i){
        int j=f[i];
        while(j && p[i]!=p[j]) j=f[j];
        f[i+1] = p[i]==p[j]?1+j:0;
    }
}
int find(char *T,char *p,int *f){
    getFail(p,f);
    int n=strlen(T);
    int m=strlen(p);
    int j=0;
    for(int i=0; i<n; ++i){
        while(j && T[i]!=p[j]) j=f[j];
        if(T[i]==p[j])++j;
    }
    return j;
}  

int main(){
    while(scanf("%s %s",s1,s2)!=EOF){
        int x=find(s2,s1,f);
        if(!x) puts("0");
        else{
            int len=strlen(s2);
            printf("%s %d\n",s2+len-x,x);
        }
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索算法
， 字符串
， int
， include
， 字符
， 前缀
， 算法 ccf acm
， acm算法数据结构
， 算法题
javascript算法题
the simpsons、simpsons、the simpsons潮牌官网、the simpsons 28、the simpsons官网，以便于您获取更多的相关知识。