题目描述

难度分:$1700$

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

删除$s$中的最长子串，使得$t$仍然是$s$的子序列，输出这个最长子串的长度。

输入样例$1$

bbaba
bb

输出样例$1$

3

输入样例$2$

baaba
ab

输出样例$2$

2

输入样例$3$

abcde
abcde

输出样例$3$

0

输入样例$4$

asdfasdf
fasd

输出样例$4$

3

算法

双指针+前后缀分解

令$s$串的长度为$n$，$t$串的长度为$m$，预处理出$pre$和$suf$两个$O(n)$级别的数组。$pre[i]$表示$s$的前缀$[1,i]$匹配了$t$的前缀$[1,pre[i]]$，$suf[i]$表示$s$的后缀$[i,n]$匹配了$t$的后缀$[suf[i],m]$。

先考虑删除前后缀的情况，遍历$i \in [1,n]$，一旦满足$pre[i]=m$，说明删除$s$的后缀$(i,n]$可以使得$t$是$s$前缀$[1,i]$的子序列，维护$n-i$的最大值。倒序遍历$i \in [1,n]$，一旦满足$suf[i]=1$，说明删除$s$的前缀$[1,i)$可以使得$t$是$s$后缀$[i,n]$的子序列。

最后是一般情况，我们希望某个$s$的前缀$[1,i]$能够匹配$t$的前缀，而这个$t$剩下的那部分，由某个$s$的后缀$[j,n]$完成匹配，这时候由$pre[i]+1=suf[j]$成立，维护$j-i-1$的最大值。还是倒序遍历$i \in [1,n]$，对于某个$i$，为了快速求得这个$j$，可以开一个哈希表$mp$存储$suf$的值。当遍历到$i$时，看看$pre[i]+1$是否在哈希表中，在就说明存在符合条件的$j$。为了让$j-i-1$尽可能大，只有在$suf[i]$第一次出现的时候，存储$mp[suf[i]]=i$。

复杂度分析

时间复杂度

双指针匹配子序列，预处理出$pre$和$suf$两个数组，时间复杂度为$O(n+m)$。后续求答案遍历了$3$遍数组，一共三种情况：删除前缀、删除后缀、删除中间段。时间复杂度是$O(n)$的，因此整个算法的时间复杂度为$O(n+m)$。

空间复杂度

除了输入的$s$串和$t$串，开辟的辅助空间主要在于$pre$数组和$suf$数组，都是$O(n)$级别的。存$suf$值的哈希表$mp$，在最差情况下会存$O(n)$级别的键值对。因此，算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, m, pre[N], suf[N];
char s[N], t[N];

int main() {
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    n = strlen(s + 1);
    m = strlen(t + 1);
    for(int i = 1; i <= n; i++) {
        pre[i] = suf[i] = -1;
    }
    pre[0] = 0;
    suf[n + 1] = m + 1;
    int i = 1, j = 1;
    while(i <= n && j <= m) {
        if(s[i] == t[j]) {
            pre[i] = j;
            j++;
        }
        i++;
    }
    i = n, j = m;
    while(i >= 1 && j >= 1) {
        if(s[i] == t[j]) {
            suf[i] = j;
            j--;
        }
        i--;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        if(pre[i] == m) {
            ans = n - i;
            break;
        }
    }
    for(int i = n; i >= 1; i--) {
        if(suf[i] == 1) {
            ans = max(ans, i - 1);
            break;
        }
    }
    unordered_map<int, int> mp;
    for(int i = n; i >= 1; i--) {
        if(mp.count(pre[i] + 1)) {
            ans = max(ans, mp[pre[i] + 1] - i - 1);
        }
        if(!mp.count(suf[i])) {
            mp[suf[i]] = i;
        }
    }
    printf("%d\n", ans);
    return 0;
}