Codeforces Round #402 (Div. 2)D. String Game 二分

题目链接:

http://codeforces.com/contest/779/problem/D

题意:

给两个串，给出删掉第一个串的第几位的序列，问最多能删除几次使得第二个串还是第一个的子序列

题解:

二分 KMP不会= =
就照着没用kmp的人写了一下当时没敢写 md ！

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 2e5+10;
17 
18 string s1,s2,s3;
19 int c[maxn];
20 
21 bool check(int l1,int l2){
22     int i=0,j=0;
23     while(i<l1 && j<l2){
24         if(s1[i]==s2[j])
25             j++;
26         i++;
27     }
28     if(j == l2)
29         return true;
30     else
31         return false;
32 }
33 
34 int main(){
35     cin >> s1 >> s2;
36     int len1 = s1.size();
37     for(int i=0; i<len1; i++){
38         int x; cin >> x;
39         c[i] = --x;
40     }
41 
42     s3 = s1;
43     int len2 = s2.size();
44     int ans = 0;
45     int le=0,ri=len1;
46     while(le<=ri){
47         int mid = (le+ri)/2;
48         for(int i=0; i<mid; i++){
49             s1[c[i]] = '*';
50         }
51 
52         if(check(len1,len2)){
53             ans = max(mid,ans);
54             le = mid+1;
55         }else{
56             ri = mid-1;
57         }
58         for(int i=0; i<mid; i++){
59             s1[c[i]] = s3[c[i]];
60         }
61     }
62 
63     cout << ans << endl;
64 
65     return 0;
66 }