计蒜客习题：首尾相接_蒜头君需要完成一个任务,任务给出两个长度均为 n 的字符串 , s,t,

问题描述

蒜头君有两个字符串 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 <iostream>
#include <string.h>
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 < n && s[j] == s[1 + j]; ++j);
    Next[1] = j;
    k = 1;
    for(i = 2; i < n; ++i) {
        int len = k + Next[k], L = Next[i - k];
        if (L < len - i) {
            Next[i] = L;
        } else {
            for (j = max(0, len - i); i + j < n && s[j] == s[i + j]; ++j);
            Next[i] = j;
            k = i;
        }
    }
    Next[0] = n;
}

void ex_kmp(char *T, char *s) {
    int n = strlen(T), m = strlen(s);
    int i, j, k;
    for(j = 0; j < n && j < m && T[j] == s[j]; ++j);
    extend[0] = j;
    k = 0;
    for (i = 1; i < n; ++i) {
        int len = k + extend[k], L = Next[i - k];
        if(L < len-i) {
            extend[i] = L;
        } else {
            for (j = max(0, len - i); j < m && i + j < n && s[j] == T[i + j]; ++j);
            extend[i] = j;
            k = i;
        }
    }
}

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 < ans; ++i) {
    cout<<s[i];
    }
    if(ans==0)cout<<"0";
    else    cout<<" "<<ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60