题意：
给出a.b两个字符串，要求删除b中某段连续的子串使得得到的b串是a中的子串。询问满足条件的最长的a的子串
思路：
在网上看了好半天各位的博客，才知道二分竟然能这么用。真是厉害了！
将b的删除问题转化：
b的前缀 + 删除部分长度+ b的后缀部分
预处理：b的前缀串在a中需要的长度
b的后缀串在a中需要的长度
二分：删除部分的长度（因为二分只能处理线性有序问题），此题无论是前缀串的处理还是后缀穿的处理都是一个线性递增的数组，因此可以用二分枚举长度
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 2e5+5; char a[maxn],b[maxn]; int pre[maxn],suf[maxn]; int main(){ scanf("%s%s",a+1,b+1); int n = strlen(a+1); int m = strlen(b+1); int pos=0; for(int i=1 ;b[i];i++,pos++) { while(pos<=n&&a[pos]!=b[i] ) pos++; pre[i]=pos; } pos=n+1; for(int i=m ;b[i];i--,pos--) { while(pos>0&&b[i]!=a[pos] ) { pos--; } suf[i]=pos; } suf[m+1] =n+1; int ans1=m+1,ans2=0,l= 0,r = m; while(l <= r) { int mid = l+r >> 1,i; for(i=0;i+mid <= m;++i) if(pre[i] < suf[i+mid+1]) break; if(i + mid <= m){ ans1 = i,ans2 = i+mid+1,r = mid-1; } else l = mid+1; } if(ans2 - ans1 > m) putchar('-'); else { for(int i=1;i<=ans1;++i) putchar(b[i]); for(int i=ans2;b[i];++i) putchar(b[i]); } return 0; }
