Visits: 133

计蒜客 – 首尾相接

蒜头君有两个字符串 $S_1$ 和 $S_2$，蒜头君想把 $S_1$ 接到 $S_2$ 后面。因为 $S_1$ 前面有一些字符和 $S_2$ 后面的一些字母一样，所以蒜头君在连接的时候就没必要重复了，比如 $S_1$ 为 cdefgh，$S_2$ 为 abcde，那么 cde 这部分就是最长的重复部分，蒜头君可以将这两个串连接为 abcdefgh。现在，给你串 $S_1$ 和串 $S_2$，请你帮蒜头君找出最长重复部分的长度。

输入格式

共两行，每行一个字符串，由小写字母构成，第一行表示串 $S_1$，第二行表示串 $S_2$。

$(1\leq |S_1|,|S_2|\leq 50000)$

riemann
marjorie

输出格式

答案输出在一行，先输出重复的字符串，再输出其长度，中间以空格隔开。若该串为空，只需输出 $0$。

rie 3

这题用 KMP 或者拓展 KMP 都能做。

直接用 KMP 好了，简单点。

首先把 $s1$ 和 $s2$ 依次拼接，然后对拼接成的字符串做一次 getNext()，该数组最后一个元素的值就是答案，因为它表示它所对应的字符之前有多少个，与该字符串开头的那么多个是一样的，这显然与题目要求的重复部分是相同的，因此直接输出 next[len3] 即可，对应的字符串就是开头的那么多个。

#include <bits/stdc++.h>

#define MAX_LEN 50007

// 以字符串 t 求 next 数组，n 为字符串长度
int* getNext(const char* t, int length) {
    int* next = (int*)malloc(sizeof(int) * (length + 1));
    next[1] = 0;
    for(int i = 2; i <= length; i++) {
        int j = next[i - 1];
        while(t[j + 1] != t[i] && j > 0) {
            j = next[j];
        }
        if(t[j + 1] == t[i]) {
            next[i] = j + 1;
        } else {
            next[i] = 0;
        }
    }
    return next;
}

// 拼接两个字符串
char* concat(const char* s1, const char* s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    char* s3 = (char*)malloc(sizeof(char) * (len1 + len2 + 2));
    strncpy(s3 + 1, s1, len1);
    strncpy(s3 + 1 + len1, s2, len2);
    s3[1 + len1 + len2] = '\0';
    return s3;
}


void print(const char * t, const int* next, int n) {
    for (int i = 1; i <= n; i++) {
        printf("%c%c", t[i], i == n ? '\n' : '\t');
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", next[i], i == n ? '\n' : '\t');
    }
}

int main() {
    char s1[MAX_LEN], s2[MAX_LEN];
    scanf("%s%s", s1, s2);
    char* s3 = concat(s1, s2);
    int len3 = strlen(s3 + 1);
    int* next3 = getNext(s3, len3);
//    print(s3, next3, len3);
    int ans = next3[len3];
    if (ans > 0) {
        for (int i = 0; i < ans; i++) {
            printf("%c", s1[i]);
        }
        printf(" ");
    }
    printf("%d", ans);
}