题目描述

难度分:$2100$

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

删除$t$的一个最短的连续子串，使得$t$是$s$的子序列。

输出删除子串后的$t$。

如果必须把$t$全部删除，输出-（减号）。

输入样例$1$

hi
bob

输出样例$1$

-

输入样例$2$

abca
accepted

输出样例$2$

ac

输入样例$3$

abacaba
abcdcba

输出样例$3$

abcba

算法

双指针+二分答案

令$s$的长度为$n$，$t$的长度为$m$。我们可以预处理出两个$O(m)$级别的数组$pre$和$suf$，$pre[i]$表示$t$的前缀$[1,i]$出现在$s$的前缀$[1,pre[i]]$中，$suf[j]$表示$t$的后缀$[j,m]$出现在$s$的后缀$[suf[j],m]$中，那如果我们想要保留$t$的前缀$[1,i]$和后缀$[j,m]$，就要删除$j-i-1$的长度，删除的子段为$(i,j)$。而这两段前缀和后缀作为$s$的一个有效的子序列，必须还要满足$pre[i] \lt suf[j]$，这样前缀和后缀作为的子序列在$s$中才不会交叠。

因此，就很容易发现单调性，肯定是给的窗口越小，越难做到让$t$删除这段子串后能够成为$s$的子序列更难。对于一个给定的删除长度$len$，我们遍历$t$上长度为$len$的所有窗口$[l,r]$，一旦满足$pre[l-1] \lt suf[r+1]$，说明将$t$的子串$[l,r]$删除后，剩余的前后缀拼起来是$s$的一个子序列，同时记录此时删除段的左右端点：

1. 如果对于$len$，能够找到$t$的一个有效删除段，就记录左右端点，并往左搜索看看有没有更短的删除段。
2. 否则说明$len$给的太小了，往右搜索更大的删除长度。

要处理出$pre$和$suf$两个数组只需要做两次子序列匹配的相向双指针即可，以$pre$数组为例进行说明。令$s$的指针$i=1$，$t$的指针$j=1$，$i$不断右移，$j$只有在满足$s[i]=t[j]$时才右移，说明匹配到了$t$的一个字符。这时候记录$pre[j]=i$，说明$t$的前缀$[1,j]$已经被$s$的前缀$[1,i]$匹配完了，$t[1…j]$是$s[1…i]$的子序列。

复杂度分析

时间复杂度

两次相向双指针预处理出$pre$和$suf$两个数组，时间复杂度为$O(n+m)$。初始化答案为删除前后缀的情况，时间复杂度为$O(m)$。在$[1,m]$上二分答案，每次$check$需要滑动窗口遍历$[w,n]$（其中$w$为窗口长度），时间复杂度为$mlog_2m$。

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

空间复杂度

除了输入的两个字符串$s$和$t$，空间瓶颈主要在于$pre$数组和$suf$数组，它们的空间消耗为$O(m)$。所以整个算法的额外空间复杂度为$O(m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int n, m, pre[N], suf[N], len, low, high;
char s[N], t[N];

bool is_sub_seq() {
    int i = 1, j = 1;
    while(i <= n && j <= m) {
        if(s[i] == t[j]) j++;
        i++;
    }
    return j > m;
}

bool check(int len) {
    for(int r = len; r <= m; r++) {
        int l = r - len + 1;
        if(pre[l - 1] < suf[r + 1]) {
            low = l, high = r;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    if(is_sub_seq()) {
        // t本来就是s的子序列，不用删除任何子串
        puts(t + 1);
        return 0;
    }
    if(n == 1) {
        bool ok = false;
        for(int i = 1; i <= m; i++) {
            if(s[1] == t[i]) {
                ok = true;
                break;
            }
        }
        puts(ok? s + 1: "-");
        return 0;
    }
    for(int i = 0; i <= m + 1; i++) {
        pre[i] = n + 1, suf[i] = -1;
    }
    int i = 1, j = 1;
    pre[0] = 0, suf[m + 1] = n + 1;
    while(i <= n && j <= m) {
        if(s[i] == t[j]) {
            pre[j] = i;
            j++;
        }
        i++;
    }
    i = n, j = m;
    while(i >= 1 && j >= 1) {
        if(s[i] == t[j]) {
            suf[j] = i;
            j--;
        }
        i--;
    }
    low = 1, high = m, len = m;
    for(int i = 1; i <= m; i++) {
        if(pre[i] <= n && m - i < len) {
            len = m - i;
            low = i + 1, high = m;
        }
    }
    for(int i = m; i >= 1; i--) {
        if(suf[i] >= 1 && i - 1 < len) {
            len = i - 1;
            low = 1, high = i - 1;
        }
    }
    int l = 1, r = m - 1;
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) {
            r = mid;
        }else {
            l = mid + 1;
        }
    }
    if(low == 1 && high == m) {
        puts("-");
    }else {
        for(int i = 1; i <= m; i++) {
            if(i < low || i > high) {
                printf("%c", t[i]);
            }
        }
    }
    return 0;
}