题目描述
难度分:1400
输入两个长度都≤2×105的字符串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′|>1且|t′|>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(Σ),Σ为字符集大小,本题取值为26,每个字母更新答案时时间复杂度为O(1)。
综上,整个算法的时间复杂度为O(n+m+Σ)。
空间复杂度
空间消耗就是pre和suf两个哈希表,额外空间复杂度为O(Σ)。
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;
}