题目描述

难度分:$1400$

输入两个长度都$\leq 2 \times 10^5$的字符串$s$和$t$，只包含小写英文字母。

输出一个最短的字符串$X$，满足$X=p+q=p’+q’$，其中$p$和$p’$是$s$的两个不同前缀，$q$和$q’$是$t$的两个不同后缀。

例如$s=$sarana，$t=$olahraga，那么$X=$saga，因为$X=$s$+$aga$=$sa$+$ga。

如果答案不止一个，输出其中任意一个。如果答案不存在，输出$-1$。

输入样例$1$

sarana
olahraga

输出样例$1$

saga

输入样例$2$

berhiber
wortelhijau

输出样例$2$

berhijau

输入样例$3$

icpc
icpc

输出样例$3$

icpc

输入样例$4$

icpc
jakarta

输出样例$4$

-1

算法

贪心

这个题看着挺唬人的，容易被卡住。比较容易发现的一点就是，我们需要确定一个$s$的前缀$s’$，这个前缀的后缀是$t$某个后缀$t’$的前缀，此时$s’$就是$p$和$p’$较长的那个，$t’$就是$q$和$q’$较长的那个。让$s’$和$t’$前后拼接，将中间的交集只保留一份，得到的最短串就是答案。

但此时无法确定这段公共部分多长是优的，我们唯一能确定的只有$|s’| \gt 1$且$|t’| \gt 1$，我也在这一步卡了很久。然后突然发现其实只要交一个字母就好了，$s’$最后一个字母$c$是$s$串后缀$[1,n)$中（$0$索引开始）第一次出现的位置，$t’$的第一个字母是$t$串前缀$[0,m-1)$中最后一次出现的位置。

所以，可以预处理出两个映射$pre$、$suf$，$pre[c]$表示字母$c$在$s[1…n-1]$中第一次出现的位置，$suf[c]$表示字母$c$在$t[0…m-2]$上最后一次出现的位置。如果不存在既在$pre$中又在$suf$中的字母$c$，肯定就无解了，否则维护长度最小的$X$就可以了。

复杂度分析

时间复杂度

预处理出$pre$和$suf$两个表的时间复杂度为$O(n+m)$，遍历一遍$s$和$t$两个串就行。然后遍历交集字母，遍历一个哈希表$pre$或$suf$就行，时间复杂度为$O(\Sigma)$，$\Sigma$为字符集大小，本题取值为$26$，每个字母更新答案时时间复杂度为$O(1)$。

综上，整个算法的时间复杂度为$O(n+m+\Sigma)$。

空间复杂度

空间消耗就是$pre$和$suf$两个哈希表，额外空间复杂度为$O(\Sigma)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    unordered_map<char, int> pre, suf;
    for(int i = 1; i < n; i++) {
        if(!pre.count(s[i])) {
            pre[s[i]] = i;
        }
    }
    for(int i = m - 2; i >= 0; i--) {
        if(!suf.count(t[i])) {
            suf[t[i]] = i;
        }
    }
    int mn = -1, l, r;
    for(auto&[c, i]: pre) {
        if(suf.count(c)) {
            int j = suf[c];
            if(mn == -1) {
                mn = i + n - j;
                l = i, r = j;
            }else {
                if(i + n - j < mn) {
                    mn = i + n - j;
                    l = i, r = j;
                }
            }
        }
    }
    if(mn == -1) {
        cout << "-1\n";
    }else {
        cout << s.substr(0, l) + t.substr(r) << endl;
    }
    return 0;
}