洛谷八连测R6

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
const int maxm=1e3+5;
int a[maxn],b[maxn],head[30],nxt[maxn][30],f[maxm][maxm];
int main(){
    int n=0,m=0; char ch;
    while(ch=getchar(),ch!='\n') a[++n]=ch-'a';
    while(ch=getchar(),ch!='\n') b[++m]=ch-'a';
    memset(head,0x3f,sizeof(head));
    for(int i=n;i>=0;--i){
        for(int j=0;j<26;++j)
        nxt[i][j]=head[j];
        head[a[i]]=i;
    }
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=m;++i) f[i][0]=0;
    for(int i=1;i<=m;++i)
    for(int j=1;j<=i;++j){
        f[i][j]=f[i-1][j];
        if(f[i-1][j-1]<=n)
        f[i][j]=min(f[i][j],nxt[f[i-1][j-1]][b[i]]);
    }
    int ans=0,l=0,r=m;//这儿暴力判断也行的
    while(l<=r){
        int mid=(l+r)>>1;
        if(f[m][mid]<=n){ans=mid; l=mid+1;}
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}