【题目类型】二分答案
&题解:
只要你想到二分答案就不是难题了,但我当时确实是想不到.
【时间复杂度】\(O(nlogn)\)
&代码:
#include <cstdio>#include <cmath>#include <iostream>#include <cstring>#include <vector>#include <algorithm>using namespace std;#define INF 0x3f3f3f3f#define ll long longconst int maxn= 2e5 +9;string s,e;int a[maxn],n,m;bool vis[maxn];bool ok(int mid){memset(vis,0,sizeof(vis));for(int i=0;i<mid;i++){vis[a[i]-1]=1;}int j=0;for(int i=0;i<n;i++){if(!vis[i]&&e[j]==s[i]){j++;}}return j==m?true:false;}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);// freopen("C:\\Users\\Zmy\\Desktop\\in.txt", "r", stdin);cin>>s>>e;n=s.size();m=e.size();for(int i=0;i<n;i++) cin>>a[i];//这里的l和r是闭区间,也就是[l,r] 代表着范围,当然 如果增加一个也可以int l=-1,r=n;while(l<=r){int mid=l+r>>1;//这要注意l和r的顺序,不能写反了if(ok(mid)) l=mid+1;else r=mid-1;}cout<<r<<endl;return 0;}