[开发工具]CF778A 题解

Idea

我们知道，这里的子串可以是不连续的！

所以，删的字符少了没有任何问题。所以我们可以二分。

我们二分的 $t$ 就是答案。我们知道要从序列 $a$ 取出一个前缀。所以，它的后缀一定是没有删除的。

于是，我们往一个 vector 里面扔 $t$ 到 $n$ 的后缀，排序，就得到了保留的序列。

再和目标字符串 $p$ 一一比对，就可以了。

Code：

#include <bits/stdc++.h>
using namespace std;
string s, p;
int a[2000001];
bool vis[2000001];
vector<int> vec;
bool check(int tar){
    vec.clear();
	for(int i = tar;i < s.length();i++){
		vec.push_back(a[i]);
	}
	sort(vec.begin(), vec.end());
	int r = 0;
	for(int i = 0;i < vec.size() && r < p.length();i++){
		if(s[vec[i] - 1] == p[r]){
			r++;
		}
	}
	if(r == p.length()){
		return true;
	}
	return false;
}
int main(){
    cin >> s >> p;
    for(int i = 0;i < s.length();i++){
        cin >> a[i];
    }
    int l = 0, r = s.length();
    while(l < r - 1){
    	int mid = (l + r) >> 1;
    	if(check(mid)){
    		l = mid;
		}
		else{
			r = mid;
		}
	}
	if(check(r)){
		cout << r << endl;
	}
	else{
		cout << l << endl;
	}
	return 0;
}