題目#
有兩個字串 \(t\) 和 \(p\) \((1 \leq |p| \leq |t| \leq 200000)\)，還有一個序列 \(a_1 … a_{|t|}\) \((1 \leq a_i \leq |t|)\)。每一次會依照序列刪除 \(t\) 裡面的數字，請求出最多可以刪除幾次使得新的 \(t\) 仍舊包含 \(p\)。（在每一次刪除資源後，編號不會改變）
（這裡的「包含」和平常的包含不一樣，這邊是指如果字串 \(s\) 能在刪除一些字元後得到字串 \(t\)，則 \(s\) 包含 \(t\)。）
解題思路#
一個一個刪除再檢查的時間複雜度為 \(O(t^2)\)，太慢了。這時候一樣可以對答案二分搜。
如果刪除完 \(k\) 次後，\(t\) 還包含 \(p\)，則刪除 \(k\) 次以內 \(t\) 也一定包含 \(p\)。刪除 \(k\) 次後，\(t\) 不包含 \(p\)，則刪除 \(k\) 次以上的 \(t\) 也一定不會包含 \(p\)。
用對答案二分搜的技巧，時間複雜度優化成 \(O(tlog(t))\)。
常見錯誤#
- 在刪除字元以後編號不會改變
- 要注意字串的 \(index\) 還有 \(a_i\) 是從 \(1\) 還是從 \(0\) 開始
完整程式碼#
#include <bits/stdc++.h>
using namespace std;
int main() {
string t, p;
cin >> t >> p;
vector<int> order(t.size());
for (int i = 0; i < t.size(); i++) {
cin >> order[i];
}
int l = 0, r = t.size();
while (l < r) {
int m = (l + r + 1) / 2;
vector<int> deleted(t.size());
for (int i = 0; i < m; i++) {
deleted[order[i] - 1] = 1;
}
int cur = 0;
for (int i = 0; i < t.size() && cur < p.size(); i++) {
if (!deleted[i] && p[cur] == t[i]) {
cur++;
}
}
if (cur == p.size()) {
l = m;
}
else{
r = m - 1;
}
}
cout << l << "\n";
}
