C. Two strings-二分的威力，思路题

Educational Codeforces Round 17 C. Two strings
题意，给两个长度小于十万的字符串A、B，B删除连续的字符串后成为A的子串（不需要连续），求这最长子串，可能为空也可能为A本身。
思路：枚举B的子串其实只要枚举删除的位置就好了，因为B删除的部分是连续的字符串而且只能删一次。可以把字符串B看成三部分。

                    | 左边部分 || 删除部分 || 右边部分 |

左边部分、右边部分可能为空。
其实就是前后缀，先求出B各个前缀需要A前缀的长度，再求出B各个后缀需要A后缀的长度，

比如说字符串A是 abacaba，字符串B是 abcdcba ，B的前缀依次是a、ab、abc、abcd….,后缀依次是a、ba、cba、dcba、cdcba….，前缀a需要字符串A的前缀长度为1(a)，前缀ab需要字符串A的前缀长度为2(ab),前缀abc需要字符串A的前缀长度为4(abac)….

后缀同理，那么，只需要满足从b前、后缀数组里面选出两个位置相加要求长度小于等于字符串A长度，这两个位置就能确定删除部分了。用len来表示B删除连续字符串后剩下的长度。

先贴一下我test 36 TLE的代码，原因是轮询太慢，2000ms，

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long int ll;
const int maxn = 100007;
char a[maxn],b[maxn];
int lena,lenb;
int needApreLen[maxn],needAsufLen[maxn];
int main()
{
//  freopen("in.txt","r",stdin);
    scanf("%s",a);
    scanf("%s",b);
    lena = strlen(a);
    lenb = strlen(b);
    for(int i=0;i<maxn;++i)needApreLen[i] = lena + 5;
    for(int i=0;i<maxn;++i)needAsufLen[i] = lena + 5;

    int pos = 0;
    for(int i = 0; i < lenb;++i)
    {
        while(pos<lena && a[pos] != b[i])++pos;
        ++pos;              //index starts from 0,plus before update
        if(pos<=lena)needApreLen[i] = min(pos,needAsufLen[i]);
        if(pos>lena)break;  
    }

    pos = lena - 1;
    for(int i = lenb-1;i >= 0;--i)
    {
        while(pos>=0 && a[pos] != b[i])--pos;       
        if(pos>=0)needAsufLen[i] = min(lena - pos,needAsufLen[i]);
        --pos;              //index starts from lena-1,decrease after update
        if(pos<0)break; 
    }

    //for(int i = 0;i < lenb;++i)printf("%d ",needApreLen[i]);printf("\n");
    //for(int i = 0;i < lenb;++i)printf("%d ",needAsufLen[i]);printf("\n");

    int longestL = -1,longestR = -1;
    for(int i = 0;i < lenb;++i)if( needApreLen[i] <= lena )longestL = i;
    for(int i = lenb - 1;i >= 0;--i)if( needAsufLen[i] <= lena )longestR = i; 

    if(longestL == -1 && longestR == -1)printf("-");
    else if(longestL == -1){//only suffix
        for(int i=longestR;i<lenb;++i)printf("%c",b[i]);
    }else if(longestR ==-1){//only prefix
        for(int i=0;i<=longestL;++i)printf("%c",b[i]);
    }
    else{
        int len,left,right,op=0,os=0;
        if(longestL+1 > lenb-longestR){     //only prefix
            len = longestL+1;
            left = longestL;
            op = 1;
        }else{      //only suffix
            len = lenb-longestR;
            right = longestR;
            os = 1;
        }
    //  printf("lenb = %d\n",lenb);
    //  printf("longestL = %d longestR = %d\n",longestL,longestR);
    //  printf("len = %d\n",len);
        for(int i = longestL,j = longestR;i>=0;--i)//i : max len of valid prefix,j : max len of valid suffix
        {
            j = longestR;
            while(j<lenb  &&needApreLen[i] + needAsufLen[j] > lena)++j;     
            if(j<lenb  && i<j && lenb-(j-i-1)>len){             
                left = i;
                right = j;
                len = lenb-(j-i-1);
                os = op = 0;
            }
        }
        if(os==0 && op==0){ 
        //  printf("here1\n");      
            for(int i=0;i<=left;++i)printf("%c",b[i]);
            for(int i=right;i<lenb;++i)printf("%c",b[i]);
        }else if(op){
        //  printf("here2\n");
            for(int i=0;i<=left;++i)printf("%c",b[i]);
        }else if(os){
        //  printf("here3\n");
            for(int i=right;i<lenb;++i)printf("%c",b[i]);
        }


    }
    printf("\n");
    return 0;
}

后来用二分查找重新优化了31ms过。。。二分真的很快，但是upper_bound用起来需要注意是否越界，而且需要先排序，而且处理字符串，从1开始存的话方便很多，不要怕错，用多了就会习惯了。重写几次代码也是很考毅力啊，可是做题不A等于没做，一定要写出来，况且根本就没有努力到需要讲求天赋的水平，优秀的人只是愿意比你多试几次而已，一点点的积累很重要，一天一点，一年会改变很多。没天赋的人需要努力，有天赋的就更需要了，不然浪费。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int ll;
const int maxn = 100050;
char a[maxn],b[maxn];
int lena,lenb;
int needAP[maxn],needAS[maxn];
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%s",a+1);
    scanf("%s",b+1);
    lena = strlen(a+1);
    lenb = strlen(b+1);
    for(int i=1;i<=lenb;++i)needAP[i] = needAS[i] = lena + 1;

    int pos = 1,longestL = lenb,longestR = 1;
    for(int i = 1; i <= lenb;++i){
        while(pos<=lena && a[pos] != b[i])++pos;
        if(pos<=lena)needAP[i] = pos;
        else {longestL = i-1;break;}
        ++pos;
    }

    pos = lena;
    for(int i = lenb;i >= 1;--i){
        while(pos>=1 && a[pos] != b[i])--pos;       
        if(pos>=1)needAS[i] = lena - pos + 1;
        else {longestR = i+1;break;}
        --pos;      
    }

    if(longestL < 1 && longestR > lenb)printf("-");
    else if(longestL == lenb || longestR == 1)printf("%s",b+1);
    else {
        int len,left,right;
        if(longestL > lenb - longestR + 1){//only prefix
            len = longestL;
            left = longestL;
            right = lenb + 1;
        }else{                              //only suffix
            len = lenb - longestR + 1;
            left = 0;
            right = longestR;
        }

        int pfind = 0;
        for(int i=longestR;i<=lenb;++i)
        {
            pfind = upper_bound(needAP,needAP+longestL+2,lena - needAS[i]) - needAP - 1;
            if(pfind <= longestL && pfind + lenb-i+1 > len){
                left = pfind;
                right = i;
                len = pfind + lenb-i+1;
            }
        }

        for(int i = 1;i <= left;++i)printf("%c",b[i]);
        for(int i = right; i<= lenb;++i)printf("%c",b[i]);
    }   
    printf("\n");
    return 0;
}