Description

给定A,B两个串，设LCS（A,B）=n 求A中所有长度为 n 的子序列（共2^n个）中，有多少个是B串的子序列 串长<=1000

Analysis

相当于在A中选n个位置，与B中n个位置进行匹配 设状态(x,y,z)表示A匹配到x，B匹配到y，已匹配个数为z的方案 考虑A中第x个选不选，不选转移到(x+1,y,z) 选转移到(x+1,p+1,z+1)，p是b[y~n]中最小使b[p]=a[x]的位置 由于当状态(x,y,z)中z< LCP(A[1~x],B[1~y])时，肯定不优 所以状态表示可优化成2维 那么写dp或者记忆化搜索都是资瓷的 状态O(N^2)个，转移O(1)

Code

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) #define efo(i,v) for(int i=last[v];i;i=next[i]) #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; typedef long long ll; const int N=1005,mo=1e9+7; int n,ans,la,lb,f[N][N],nxt[N]['z'+5]; ll g[N][N]; bool bz[N][N]; char a[N],b[N]; ll dfs(int x,int y,int l) { if(l<f[x-1][y-1]) return 0; if(x>la+1 || y>lb+1) return 0; if(l>=n) return 1; int p=nxt[y][a[x]]; ll t=0; if(p && l+1>=f[x][p]) { if(bz[x+1][p+1]) t=(t+g[x+1][p+1])%mo; else t=(t+dfs(x+1,p+1,l+1))%mo; } if(bz[x+1][y]) t=(t+g[x+1][y])%mo; else t=(t+dfs(x+1,y,l))%mo; g[x][y]=t,bz[x][y]=1; return t; } int main() { scanf("%s\n%s",a+1,b+1); la=strlen(a+1),lb=strlen(b+1); fd(i,lb,1) { fo(j,'a','z') nxt[i][j]=(i+1<=lb)?nxt[i+1][j]:(lb+1); nxt[i][b[i]]=i; } fo(i,1,la) fo(j,1,lb) { f[i][j]=max(f[i-1][j],f[i][j-1]); if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1); } n=f[la][lb]; printf("%lld",dfs(1,1,0)); return 0; }