String Game 题解

题目传送门

一道二分题。

\(|p|\le2\times10^6\)，考虑 \(O(n\log n)\) 的算法，而又要输出最大值，不难想到二分答案。

二分删除字母的数量，用一个数组将删掉的字母的下标存起来，然后判断删除字符后的 \(t\) 是否是 \(p\) 的子序列即可。

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
string t, p;
int ans;
int a[200005];
bool removed[200005]; // removed[i] 表示 i 下标上的字母已被删除
bool check(int x) {
    if (x > t.size()) return 0;
    int cnt = 0;
    memset(removed, 0, sizeof(removed));
    for (int i = 1; i <= x; i++) removed[a[i]] = 1;
    for (int i = 0; i < t.size(); i++) {
        if (removed[i + 1]) continue; 
        if (t[i] == p[cnt]) cnt++;
    }
    if (cnt == p.size()) return 1; 
    return 0;
}
void f(int l, int r) {
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            l = mid + 1;
            ans = mid; // 求最大值
        }
        else r = mid - 1;
    }
}
signed main() {
    ios :: sync_with_stdio(0);
    cin >> t >> p;
    for (int i = 1; i <= t.size(); i++) cin >> a[i];
    f(1, 200000);
    cout << ans;
    return 0;
}