String Game

題目

有兩個字串 $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";
}