[59测试]C

题目描述

小 A 非常喜欢字符串，所以小 K 送给了小 A 两个字符串作为礼物。两个字符串分别为 X，

Y。小 A 非常开心，但在开心之余她还想考考小 K。小 A 定义L为 X 与 Y 的最长公共子序列的长度（子序列在字符串内不一定连续，一个长度为L的字符串有2^L2​L​​个子序列，包括空子序列）。现在小 A 取出了 X 的所有长度为L的子序列，并要求小 K 回答在这些子序列中，有多少个是 Y 的子序列。因为答案可能很大，所以小 K 只需要回答最终答案模109 + 7。

输入输出格式

输入格式

第一行包含一个非空字符串 X。

第二行包含一个非空字符串 Y。

字符串由小写英文字母构成。

输出格式

对于每组测试数据输出一个整数，表示对应的答案。

输入输出样例

输入样例1

aa
ab

输出样例1

2

说明

对于 20%的数据，$$1 \leq |X|,|Y| \leq 10$$；

对于 100%的数据，$$1 \leq |X|,|Y| \leq 10^3$$。

思路

dp

经典DP LCS 问题，预处理LCS。

f[i][j]:X串的前i个，Y串的前j个，长度为lcs[i][j]时的总数

若LCS[i-1][j]==LCS[i][j],f[i][j]+=f[i-1][j](第i个不选)

若LCS[i-1][p-1]+1==f[i][j],f[i][j]+=f[i-1][p-1](考虑第i个,p为Y串前j个字符中最靠后的与X[i]相同的字符的位置)

ans=f[len1][len2]

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

const int MAXNUM=1000;
const int Mod=1e9+7;
int lcs[MAXNUM+5][MAXNUM+5];
int pre[MAXNUM][28];
int pos[28];
int f[MAXNUM+5][MAXNUM+5];//s1的前i个，s2的前j个长度为lcs[i][j]的总数 
char s1[MAXNUM+5],s2[MAXNUM+5];
int len1=0,len2=0;

void get_lcs()
{
    memset(lcs,0,sizeof(lcs));
    for(int i=1;i<=len1;i++)
        for(int j=1;j<=len2;j++)
        {
            if(s1[i]==s2[j])
                lcs[i][j]=max(lcs[i][j],lcs[i-1][j-1]+1);
            else lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);    
        }
}

void get_pre()
{
    for(int i=1;i<=len2;i++)
    {
        pos[s2[i]-'a'+1]=i;
        for(int j=1;j<=26;j++)
            pre[i][j]=pos[j];
    }
}

int main()
{
//    freopen("C.in","r",stdin);
//    freopen("C.out","w",stdout); 
    scanf("%s%s",s1+1,s2+1);
    len1=strlen(s1+1),len2=strlen(s2+1);
    get_lcs();
//    cout<<lcs[len1][len2]<<endl;
    memset(pre,-1,sizeof(pre));
    get_pre();
    for(int i=0;i<=len1;i++)
        f[i][0]=1;
    for(int i=0;i<=len2;i++)
        f[0][i]=1;
    for(int i=1;i<=len1;i++)
        for(int j=1;j<=len2;j++)
        {
            if(lcs[i][j]==lcs[i-1][j])
                f[i][j]=(f[i][j]+f[i-1][j])%Mod;
            int Pre=pre[j][s1[i]-'a'+1];
            if(Pre!=-1 && lcs[i-1][Pre-1]==lcs[i][j]-1)
                f[i][j]=(f[i][j]+f[i-1][Pre-1])%Mod;
        }
    cout<<f[len1][len2]<<endl;
}