字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列<i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij = yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。对给定的两个字符序列,求出他们最长的公共子序列长度,以及最长公共子序列个数。
Solution
这题其实就是让求两个序列的LCS和方案数。
LCS的求法:
dp[i][j]=dp[i-1][j-1]+1(s[i]==s[j])
dp[i][j]=max(dp[i][j-1],dp[i-1][j])(s[i]!=s[j])
这个非常简单,但计数部分需要一些思考。
第一种情况时,我们当前的方案数位不管i位和j位的方案数(因为i和j匹配了),所以要把g[i-1][j]和g[i][j-1]讨论一下。
第二种情况,当dp[i-1][j]==dp[i][j-1]时,我们的g[i-1][j-1]的方案都被算了一次,所以要减掉。
这道题可以加深对LCS的理解。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 5004
#define mod 100000000
using namespace std;
int dp[][N],n1,n2,now;
long long g[][N];
char s1[N],s2[N];
int main(){
scanf("%s%s",s1+,s2+);
n1=strlen(s1+)-;
n2=strlen(s2+)-;
for(int i=;i<=n1;++i)g[][i]=g[][i]=;
for(int i=;i<=n1;++i){
now^=;
for(int j=;j<=n2;++j){
int f=(s1[i]==s2[j]);
if(f){
dp[now][j]=dp[now^][j-]+f;
g[now][j]=g[now^][j-];
if(dp[now^][j]==dp[now][j])(g[now][j]+=g[now^][j])%=mod;
if(dp[now][j-]==dp[now][j])(g[now][j]+=g[now][j-])%=mod;
}
else{
g[now][j]=;
dp[now][j]=max(dp[now^][j],dp[now][j-]);
if(dp[now^][j]==dp[now][j])(g[now][j]+=g[now^][j])%=mod;
if(dp[now][j-]==dp[now][j])(g[now][j]+=g[now][j-])%=mod;
if(dp[now^][j-]==dp[now][j])(g[now][j]-=g[now^][j-])%=mod;
g[now][j]=(g[now][j]+mod)%mod;
}
}
}
printf("%d\n%d",dp[now][n2],g[now][n2]);
return ;
}