题目大意
解题思路
dp求lcs很容易，关键是x串的子串只要y有一个对应就贡献1且只贡献1。考虑设g[i][j]，x串dp到i，y到j的方案数，加入x串字符时可以直接累加方案数，但需要lcs相同，加入y串字符时不可以累加，同时加入x串字符和y串字符时需要找到y串前j个字符中最后的字符，将这个状态的前一个状态转移到当前状态，即lcs小1的状态。
code
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int max(
int x,
int y){
return (x>y)?x:y;}
int min(
int x,
int y){
return (x<y)?x:y;}
int const mn=
1e3+
9,mo=
1e9+
7;
int n,m,f[mn][mn],to[mn][mn],pre[mn],tmp[mn];
LL g[mn][mn];
char a[mn],b[mn];
int main(){
freopen(
"d.in",
"r",stdin);
freopen(
"d.out",
"w",stdout);
scanf(
"%s",a+
1);n=
strlen(a+
1);
scanf(
"%s",b+
1);m=
strlen(b+
1);
fo(i,
0,n)g[i][
0]=
1;
fo(i,
0,m)g[
0][i]=
1;
fo(i,
1,n){
fo(j,
1,m){
if((i==n)&&(j==m)){
int bb;
bb++;
}
tmp[b[j]]=j;
f[i][j]=max(max(f[i][j-
1],f[i-
1][j]),f[i-
1][j-
1]+(a[i]==b[j]));
if(f[i-
1][j]==f[i][j])g[i][j]=g[i-
1][j];
if(tmp[a[i]]&&(f[i][j]==f[i-
1][tmp[a[i]]-
1]+
1))
g[i][j]=(g[i][j]+g[i-
1][tmp[a[i]]-
1])%mo;
}
fo(j,
'a',
'z')tmp[j]=
0;
}
printf(
"%lld",g[n][m]);
return 0;
}
