问题描述

蒜头君有两个字符串 S1​ 和 S2​，蒜头君想把 S1​ 接到S2​ 后面。因为 S1​ 前面有一些字符和 S2​ 后面的一些字母一样，所以蒜头君在连接的时候就没必要重复了，比如S1​ 为cdefgh，S2​ 为abcde，那么cde这部分就是最长的重复部分，蒜头君可以将这两个串连接为abcdefgh。现在，给你串S1​ 和串 S2​，请你帮蒜头君找出最长重复部分的长度。
输入格式
共两行，每行一个字符串，由小写字母构成，第一行表示串S1​，第二行表示串S2(1≤∣S1​∣,∣S2​∣≤50000)
输出格式
答案输出在一行，先输出重复的字符串，再输出其长度，中间以空格隔开。若该串为空，只需输出 0。
样例输入
riemann
marjorie
样例输出
rie 3

---

AC代码

#include 
#include 
using namespace std;
const int maxn=50050;
int Next[maxn],extend[maxn];

void get_Next(char *s) {
    int n = strlen(s);
    int i, j, k;
    for(j = 0; 1 + j 1 + j]; ++j);
    Next[1] = j;
    k = 1;
    for(i = 2; i int len = k + Next[k], L = Next[i - k];
        if (L else {
            for (j = max(0, len - i); i + j 0] = n;
}

void ex_kmp(char *T, char *s) {
    int n = strlen(T), m = strlen(s);
    int i, j, k;
    for(j = 0; j 0] = j;
    k = 0;
    for (i = 1; i int len = k + extend[k], L = Next[i - k];
        if(L else {
            for (j = max(0, len - i); j int main() {
    char s[maxn],T[maxn];
    cin>>s>>T;
    get_Next(s);
    ex_kmp(T, s);
    int ans=0; 
    for (int i = 0; i <strlen(T); ++i) {
    ans=max(ans,extend[i]);
    }
    for (int i = 0; i cout<if(ans==0)cout<<"0";
    else    cout<<" "<return 0;
}

---