Codeforces Round #402 (Div. 2) D. String Game 二分+优先队列+字符串匹配

My Solution

题意：给出文本串和目标串，然后给出一个文本串删除字符的序列，从a1~an，要求删除s[a1 ~ ak]时剩下的字符串依然可以匹配，求尽可能大的k。

二分+优先队列+字符串匹配

从左往右是删除字符的顺序，倒着做，从右往做是添加字符的顺序，故check mid~n这个序列能否满足目标串的匹配，要求mid尽可能小，

故二分这个剩余序列长度即可，每次check是用优先队列priority_queue<int, vector, greater> pq;，然后依次进行匹配。

复杂度 O(nlognlogn)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;

string t, s;
int v[maxn], n, szs;
priority_queue<int, vector, greater > pq;

inline bool check(const int &x)
{
    int i, ptr = 0;
    for(i = n; i > n - x; i--) pq.push(v[i]);
    while(!pq.empty()){
        if(s[ptr] == t[pq.top() - 1]) ptr++;
        pq.pop();
        if(ptr == szs) break;

    }
    while(!pq.empty()) pq.pop();
    if(ptr == szs) return true;
    else return false;
}

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> t >> s;
    int i;
    n = t.size(); szs = s.size();
    for(i = 1; i <= n; i++){ cin >> v[i];
    }
    int l = 0, r = n, mid;
    while(l + 1 < r){ mid = (l + r) >> 1;
        if(check(mid)){
            r = mid;
        }
        else l = mid;
    }

    if(check(l)) cout << n - l << endl;
    else if(check(r)) cout << n - r << endl;
    else cout << 0 << endl;

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx