武汉大学2022级新生程序设计竞赛 F - 最短公共超串 // kmp

题目来源：“帆软杯”武汉大学2022级新生程序设计竞赛 F

题目链接：F-最短公共超串

题意

给定两个字符串\(a\)和\(b\)，求：一个同时以\(a\)和\(b\)作为子串的最短字符串。

数据范围：\(|a|,|b|\le2·10^5\).

思路：kmp

若有\(b\)为\(a\)的子串，那么\(a\)就是答案；若有\(a\)为\(b\)的子串，那么\(b\)就是答案。快速判断一个字符串中是否存在等于另一个字符串的子串，可以用kmp算法。

若不存在以上两种情况，那么答案应该是\(a\)在前\(b\)在后，去掉中间重叠部分，或者\(b\)在前\(a\)在后，去掉中间重叠部分的形式。

对于\(a\)在前\(b\)在后的情况，实际上我们需要找出最长的同时为\(a\)后缀和\(b\)前缀的公共子串长度\(len_1\)，那么答案就是\(|a|+|b|-len_1\)。将\(b\)和\(a\)按顺序拼接起来，得到一个新的字符串，记为\(c\)，对\(c\)求一次\(next\)数组，那么\(next[|a|+|b|]\)就是\(c\)最大的相等前后缀长度，同时也是要求的\(len_1\)。

相对应的，可以得到\(b\)在前\(a\)在后的情况，求得\(len_2\)。我们要令答案尽量短，就希望重叠部分尽量长，因此取重叠部分较长的那种情况即可。

时间复杂度：\(O(|a|+|b|)\).

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 200010;

int n, m, ne[N << 1];
char a[N], b[N], c[N << 1];

int get_next(char s[], int n)
{
    ne[1] = 0;
    for(int i = 2, j = 0; i <= n; i++) {
        while(j && s[i] != s[j + 1]) j = ne[j];
        if(s[i] == s[j + 1]) ++ j;
        ne[i] = j;
    }
    return ne[n];
}

bool inString(char s1[], int n1, char s2[], int n2)
{
    for(int i = 1, j = 0; i <= n1; i++) {
        while(j && s1[i] != s2[j + 1]) j = ne[j];
        if(s1[i] == s2[j + 1]) ++ j;
        if(j == n2) return true;
    }
    return false;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> a + 1 >> b + 1;
    n = strlen(a + 1), m = strlen(b + 1);

    // b为a的子串
    get_next(b, m);
    if(inString(a, n, b, m)) {
        cout << a + 1 << endl;
        return 0;
    }

    // a为b的子串
    get_next(a, n);
    if(inString(b, m, a, n)) {
        cout << b + 1 << endl;
        return 0;
    }

    // a在前，b在后，去掉重叠部分
    for(int i = 1; i <= m; i++) c[i] = b[i];
    for(int i = 1; i <= n; i++) c[m + i] = a[i];
    int len1 = get_next(c, n + m);  // 同时为a后缀和b前缀的最大子串长度
 
    // b在前，a在后，去掉重叠部分
    for(int i = 1; i <= n; i++) c[i] = a[i];
    for(int i = 1; i <= m; i++) c[n + i] = b[i];
    int len2 = get_next(c, n + m);  // 同时为b后缀和a前缀的最大子串长度
 
    if(len1 >= len2) {
        cout << a + 1;
        for(int i = len1 + 1; i <= m; i++) cout << b[i];
    } else {
        cout << b + 1;
        for(int i = len2 + 1; i <= n; i++) cout << a[i];
    }

    return 0;
}