为了逃离无穷的轮回，Okabe和Suzuha踏上了回到1975的道路。Time machine剩余的燃料不多了，必须尽可能的利用好。燃料的利用可以用两个字符串 A 和 B 来表示，如果存在一个串 S，满足 S 同时是两个串的子序列，则 S 就是对燃料的合法利用，现在想知道最长能找出来多长的 S。
输入格式：
两行，一行一个字符串，分别表示 A 和 B。
输出格式：
一行一个整数，表示S 的长度。
#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; }
原文：http://www.cnblogs.com/huihao/p/7751560.html