D2. Remove the Substring (hard version)

题目传送门

思路很简单，只需要记下字符串t 的所有字符在不妨碍能构成s子序列的情况下的第一个位置和最后一个位置就可以了。问题是怎么实现，我们只需要从前往后遍历一遍记载第一个位置，然后从后往前遍历一遍记载第二个位置就可以了。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define inf 0x3f3f3f3f
#define pii pair<int,int>
map<int, int>mp;
set<int>st;
const int mod = 1e9 + 7,N=2e5+5;
int a[N];
pii qwq[N]; // 记录每个字符的第一个位置和最后一个位置
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    string s1, s2;
    cin >> s1 >> s2;
    int ff = s2.size() - 1;
    for (int i = s1.size() - 1; i >= 0; i--) //从后往前遍历找最后一个位置
    {
        if (s1[i] == s2[ff])
        {
            qwq[ff].second = i;
            ff--;
            if (ff < 0) break;
        }
    }
    ff = 0; //记得初始化
    for (int i = 0; i < s1.size(); i++) // 从前往后遍历找第一个位置
    {
        if (s1[i] == s2[ff])
        {
            qwq[ff].first = i;
            ff++;
            if (ff > s2.size() - 1) break;
        }
    }
    int ans = 0;
    for (int i = 0; i < s2.size(); i++)
    {
        if (i < s2.size() - 1)
        {
            ans = max(ans, qwq[i + 1].second - qwq[i].first -1);
        }
    }
    ans = max(ans, qwq[0].second );
    int len = s1.size();
    ans = max(ans, len - qwq[s2.size() - 1].first-1 ); // 三种情况找最大值
    cout << ans << endl;
    return 0;
}