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

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include <sstream>
#include<string>
#include<cstring>
#include<list>
using namespace std;
#define MAXN 51000
#define INF 0x3f3f3f3f
typedef long long LL;
/*
求两个串的最长相同前缀后缀匹配
那么可以将两个串连接起来用求Next数组的方法找出所有匹配，选可行（小于两个串长度的）的最大值
*/
char a[MAXN*2],b[MAXN*2];
int Next[MAXN*2];
void kmp_pre(char t[])
{
    int m = strlen(t);
    int j,k;
    j = 0;k = Next[0] = -1;
    while(j<m)
    {
        if(k==-1||t[j]==t[k])
            Next[++j] = ++k;
        else
            k = Next[k];
    }
}
int main()
{
    while(scanf("%s%s",a,b)!=EOF)
    {
        int l1 = strlen(a),l2 = strlen(b),L = l1+l2;
        stringstream ss;
        ss<<a<<b;
        ss>>a;
        kmp_pre(a);
        int ans = Next[L],k = L;
        if(ans>l1||ans>l2)
            ans = min(l1,l2);
        if(ans>0)
        {
            for(int i=0;i<ans;i++)
                printf("%c",a[i]);
            printf(" %d\n",ans);
        }
        else
            printf("0\n");
    }
    return 0;
}