Description
Data Constraint
Solution
我们设dp[i][j]表示最长公共子序列。正常求。同时我们设f[i][j]表示在满足当前dp[i][j]的情况下前i个x中的子序列有多少是满足是y的子序列。那么我们枚举一下：若当前的子序列中匹配不包括i，那么我们考虑若dp[i-1][j]==dp[i][j]，那么f[i][j]+=f[i-1][j]。若当前的子序列中匹配包括i，那么我们考虑i必须被匹配，所以我们在前j个字符中找一个最晚出现的满足s1[p]==s[i]的位置，若dp[i-1][p-1]+1==dp[i][j]，那么f[i][j]+=f[i-1][p-1]。
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll maxn=
1e3+
5,mo=
1e9+
7;
ll f[maxn][maxn],g[maxn][maxn];
char s[maxn],s1[maxn];
ll n,m,i,t,j,k,l,x,y,z,mx;
int main(){
scanf(
"%s\n",s+
1);
scanf(
"%s\n",s1+
1);
n=
strlen(s+
1);m=
strlen(s1+
1);
for (i=
0;i<=m;i++)g[
0][i]=
1;
for (i=
0;i<=n;i++)g[i][
0]=
1;
for(i=
1;i<=n;i++){
x=-
1;
for (j=
1;j<=m;j++){
if (s1[j]==s[i]) x=j;
f[i][j]=max(max(f[i][j-
1],f[i-
1][j]),f[i-
1][j-
1]+(s[i]==s1[j]));
if (f[i][j]==f[i-
1][j]) g[i][j]=g[i-
1][j];
if (x>
0 && f[i][j]==f[i-
1][x-
1]+
1) g[i][j]=(g[i][j]+g[i-
1][x-
1])%mo;
}
}
printf(
"%lld\n",g[n][m]);
}
