题目描述

难度分:$1500$

输入$n$，$m(2 \leq m \leq n \leq 2 \times 10^5)$，长为$n$的字符串$s$，长为$m$的字符串$t$，只包含小写英文字母。保证$t$是$s$的子序列。

设$s$中的一个等于$t$的子序列的下标为$p[0],p[1],…,p[m-1]$。定义其宽度为$max(p[i+1] - p[i])$（$i \lt m-1$）。

输出$s$中所有等于$t$的子序列中的最大宽度。

输入样例$1$

5 3
abbbc
abc

输出样例$1$

3

输入样例$2$

5 2
aaaaa
aa

输出样例$2$

4

输入样例$3$

5 5
abcdf
abcdf

输出样例$3$

1

输入样例$4$

2 2
ab
ab

输出样例$4$

1

算法

双指针

先正着用双指针（本质是个贪心，尽早匹配），把$t$在$s$中最早出现位置的索引列表抓出来，记为$low$；再反着用双指针，把$t$在$s$中最晚出现位置的索引列表抓出来（倒着最早即正着最晚），记为$high$。然后遍历$low$和$high$这两个列表，在不越界的情况下$high[i+1]-low[i]$（$i+1 \lt m$）的最大值就是答案。

复杂度分析

时间复杂度

双指针遍历$s$和$t$两次预处理出$low$数组和$high$数组，时间复杂度为$O(n+m)$。接下来同时遍历$low$和$high$求得答案，时间复杂度为$O(m)$。因此，整个算法的时间复杂度为$O(n+m)$。

空间复杂度

除了输入的$s$串和$t$串，空间消耗主要在于$low$和$high$这两个索引列表，额外空间复杂度为$O(m)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    vector<int> low, high;
    for(int i = 0, j = 0; i < n; i++) {
        if(j < m && s[i] == t[j]) {
            low.push_back(i);
            j++;
        }
    }
    for(int i = n - 1, j = m - 1; i >= 0; i--) {
        if(j >= 0 && s[i] == t[j]) {
            high.push_back(i);
            j--;
        }
    }
    reverse(high.begin(), high.end());
    int ans = 0;
    for(int i = 0; i < m - 1; i++) {
        ans = max(ans, high[i + 1] - low[i]);
    }
    cout << ans << endl;
    return 0;
}