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;
}