[CF1492C] Maximum width - 贪心

Description

有一串长度为 \(n\) 的字符串 \(s\) 和一串长度为 \(m\) 的字符串 \(t\)，保证 \(2 \leq m \leq n \leq 2*10^5\)。定义序列 \(p\) : \(p_1,p_2...p_m\) 当且仅当其满足 : 对于\(1 \leq i \leq m\)中的每个 \(i\) ，都有 \(s_{p_i}=t_i\)。定义序列 \(p\) 的宽度为 \(max(p_{i+1}-p_i)\) 其中 $1 \leq i <m $。求这个宽度的最大值。

Solution

从左向右贪心匹配到 t 的第 i 个字符，用的代价为 li，从右向左为 ri

我们考虑枚举撑得最大的那个位置，那么直接求 max(l(i)+r(i+1)) 即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);

    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    s = " " + s;
    t = " " + t;

    vector<int> l(n + 2), r(n + 2);
    int p = 1;
    for (int i = 1; i <= n && p <= m; i++)
        if (s[i] == t[p])
            l[p++] = i;
    p = m;
    for (int i = n; i >= 1 && p >= 1; i--)
        if (s[i] == t[p])
            r[p--] = i;

    int ans = 0;
    for (int i = 1; i < m; i++)
        ans = max(ans, r[i + 1] - l[i]);

    cout << ans << endl;
}