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.

clinton
homer
riemann
marjorie

0
rie 3
题意描述：
输入两个串s1和s2
计算并输出s1串的前缀和s2的后缀的最长相似部分和它的长度
解题思路：
KMP模板题，不同在于让KMP函数匹配过程中让s1跑完，最后返回最相似度j即可。
代码实现：

 1 #include<stdio.h>
 2 #include<string.h>
 3 char s1[50010],s2[50010];
 4 int kmp(char s[],char t[]);
 5 void get_next(char t[],int next[],int l);
 6 int main()
 7 {
 8     int i,j,k;
 9     while(scanf("%s%s",s1,s2) != EOF)
10     {
11         if( (k=kmp(s2,s1)) > 0 )//加括号 
12         {
13             for(i=0;i<k;i++)
14                 printf("%c",s1[i]);
15             printf(" %d\n",k);
16         }
17         else
18             printf("0\n");
19     }
20     return 0;
21 }
22 int kmp(char s[],char t[])
23 {
24     int i,j,l1,l2;
25     l1=strlen(s);
26     l2=strlen(t);
27     int next[50010];
28     get_next(t,next,l2);
29     i=0;
30     j=0;
31     while(i < l1)
32     {
33         if(j==-1 || s[i] == t[j])
34         {
35             i++;
36             j++;
37         }
38         else
39             j=next[j];
40     }
41     //printf("j=%d\n",j);
42     return j;
43 }
44 void get_next(char t[],int next[],int l)
45 {
46     int i,j;
47     i=0;j=-1;
48     next[0]=-1;
49     while( i < l)
50     {
51         if(j==-1 || t[i]==t[j])
52         {
53             i++;
54             j++;
55             next[i]=j;
56         }
57         else
58             j=next[j];
59     }
60     /*for(i=0;i<=l;i++)
61         printf("%d ",next[i]);
62     printf("\n");*/
63 }