Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware we had.
Marge: Yeah, what is it?
Homer: Take me for example. I want to find out if I have a talent in politics, OK?
Marge: OK.
Homer: So I take some politician’s name, say Clinton, and try to find the length of the longest prefix
in Clinton’s name that is a suffix in my name. That’s how close I am to being a politician like Clinton
Marge: Why on earth choose the longest prefix that is a suffix???
Homer: Well, our talents are deeply hidden within ourselves, Marge.
Marge: So how close are you?
Homer: 0!
Marge: I’m not surprised.
Homer: But you know, you must have some real math talent hidden deep in you.
Marge: How come?
Homer: Riemann and Marjorie gives 3!!!
Marge: Who the heck is Riemann?
Homer: Never mind.
Write a program that, when given strings s1 and s2, finds the longest prefix of s1 that is a suffix of s2.
题意：求两个字符串的最长公共子串
扩展KMP裸题
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; const int maxn=5e4+; char s[maxn],t[maxn];
int nxt[maxn],ext[maxn]; void EKMP(char s[],char t[],int lens,int lent){
int i,j,p,l,k;
nxt[]=lent;j=;
while(j+<lent&&t[j]==t[j+])j++;
nxt[]=j;
k=;
for(i=;i<lent;i++){
p=nxt[k]+k-;
l=nxt[i-k];
if(i+l<p+)nxt[i]=l;
else{
j=max(,p-i+);
while(i+j<lent&&t[i+j]==t[j])j++;
nxt[i]=j;
k=i;
}
} j=;
while(j<lens&&j<lent&&s[j]==t[j])j++;
ext[]=j;k=;
for(i=;i<lens;i++){
p=ext[k]+k-;
l=nxt[i-k];
if(l+i<p+)ext[i]=l;
else{
j=max(,p-i+);
while(i+j<lens&&j<lent&&s[i+j]==t[j])j++;
ext[i]=j;
k=i;
}
}
} int main(){
while(scanf("%s%s",s,t)!=EOF){
EKMP(t,s,strlen(t),strlen(s));
int l=strlen(t);
int i;
for(i=;i<l;++i){
if(ext[i]==l-i){
printf("%s %d\n",t+i,l-i);
break;
}
}
if(i==l)printf("0\n");
}
return ;
}