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;
}