Simpsons’ Hidden Talents

clinton
homer
riemann
marjorie

0
rie 3

题目大意：

给你字符串s1和s2，问你s1的前缀和s2的后缀最长相同的串多长？

牢记KMP Next数组的含义，将s1和s2拼接在一起，next[len]也就是最终答案。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <sstream>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn=51000;
int next[maxn*2];
char word[maxn*2],s1[maxn],s2[maxn];

void kmp(){
    int n=strlen(word);
    for(int i=0;i<=n;i++) next[i]=0;
    for(int i=1;i<n;i++){
        int j=i;
        while(j>0){
            j=next[j];
            if(word[j]==word[i]){
                next[i+1]=j+1;
                break;
            }
        }
    }
}

int main(){
    while(scanf("%s%s",s1,s2)!=EOF){
        stringstream ss;
        ss<<s1<<s2;
        ss>>word;
        kmp();
        int len=strlen(word),ans=min(strlen(s1),strlen(s2));
        if(next[len]<=strlen(s1) && next[len]<=strlen(s2) ){
             ans=next[len];
        }
        if(ans==0) printf("0\n");
        else{
            for(int i=0;i<ans;i++) printf("%c",s1[i]);
            printf(" %d\n",ans);
        }
    }
    return 0;
}

HDU 2594 Simpsons’ Hidden Talents （字符串-KMP）,布布扣,bubuko.com

HDU 2594 Simpsons’ Hidden Talents （字符串-KMP）

原文：http://blog.csdn.net/a1061747415/article/details/38277355