Codeforces Round #579 (Div. 3) D2. Remove the Substring (hard version)(序列自动机+贪心)

题目链接
大意：给你两个字符串 $a,b$a,b，让你在a中删除一个子串，使得b仍然是新a串的一个子序列
思路：我们用a正着跑一下序列自动机，然后倒着跑一次序列自动机。然后我们思考一下，假设我们删除的子串位于 $[l,r]$[l,r]这个区间，那么子序列如果分成了两部分的话，那么一部分的子序列就在 $[1,l)$[1,l)，一部分在 $(r,length]$(r,length]，我们就遍历序列自动机，
正着的时候更新 $L_i$Li​即子序列第i个字符最左可能在哪个位置，倒着的时候更新 $R_i$Ri​，即子序列第i个字符最右可能是哪，然后我们遍历子序列的左右分界点，取一个最大值就好啦
细节见代码

#include<bits/stdc++.h>
 
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
using namespace std;
 
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
char a[N],b[N];
int L[N],R[N];
int f[N][33],p[N][33];
int main(){
	ios::sync_with_stdio(false);
	cin>>a+1>>b+1;
	int l=strlen(a+1),r=strlen(b+1);
	for(int i=l;i>=1;i--){
		for(int j=0;j<26;j++)f[i][j]=f[i+1][j];
		f[i][a[i]-'a']=i;
	}	
	for(int i=1;i<=r;i++){
		L[i]=f[L[i-1]+1][b[i]-'a'];
	}
	for(int i=1;i<=l;i++){
		for(int j=0;j<26;j++)p[i][j]=p[i-1][j];
		p[i][a[i]-'a']=i;
	}
	R[r+1]=l+1;
	for(int i=r;i>=1;i--){
		R[i]=p[R[i+1]-1][b[i]-'a'];
	}
	int ans=0;
	for(int i=0;i<=r;i++){//左边1-i,右边i+1-r
		if(i==0){
			ans=max(ans,R[1]-1);
		}else if(i==r){
			ans=max(ans,l-L[r]);
		}else{
			ans=max(ans,R[i+1]-L[i]-1);
		}
	}
	cout<<ans<<endl;
	return 0;
}