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裸题
1 #include<stdio.h>
2 #include<string.h>
3 #include<algorithm>
4 using namespace std; 5
6 const int maxn=5e4+5; 7
8 char s[maxn],t[maxn]; 9 int nxt[maxn],ext[maxn]; 10
11 void EKMP(char s[],char t[],int lens,int lent){ 12 int i,j,p,l,k; 13 nxt[0]=lent;j=0; 14 while(j+1<lent&&t[j]==t[j+1])j++; 15 nxt[1]=j; 16 k=1; 17 for(i=2;i<lent;i++){ 18 p=nxt[k]+k-1; 19 l=nxt[i-k]; 20 if(i+l<p+1)nxt[i]=l; 21 else{ 22 j=max(0,p-i+1); 23 while(i+j<lent&&t[i+j]==t[j])j++; 24 nxt[i]=j; 25 k=i; 26 } 27 } 28
29 j=0; 30 while(j<lens&&j<lent&&s[j]==t[j])j++; 31 ext[0]=j;k=0; 32 for(i=1;i<lens;i++){ 33 p=ext[k]+k-1; 34 l=nxt[i-k]; 35 if(l+i<p+1)ext[i]=l; 36 else{ 37 j=max(0,p-i+1); 38 while(i+j<lens&&j<lent&&s[i+j]==t[j])j++; 39 ext[i]=j; 40 k=i; 41 } 42 } 43 } 44
45 int main(){ 46 while(scanf("%s%s",s,t)!=EOF){ 47 EKMP(t,s,strlen(t),strlen(s)); 48 int l=strlen(t); 49 int i; 50 for(i=0;i<l;++i){ 51 if(ext[i]==l-i){ 52 printf("%s %d\n",t+i,l-i); 53 break; 54 } 55 } 56 if(i==l)printf("0\n"); 57 } 58 return 0; 59 }