算法——最长公共子序列
链接:https://ac.nowcoder.com/acm/problem/19978
来源:牛客网
题目描述
字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。
令给定的字符序列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的一个子序列。对给定的两个字符序列,求出他们最长的公共子序列长度,以及最长公共子序列个数。
输入描述:
第1行为第1个字符序列,都是大写字母组成,以”.”结束。长度小于5000。
第2行为第2个字符序列,都是大写字母组成,以”.”结束,长度小于5000。
输出描述:
第1行输出上述两个最长公共子序列的长度。
第2行输出所有可能出现的最长公共子序列个数,答案可能很大,只要将答案对100,000,000求余即可。
源码:
#include<cstdio>
#include<cstring>
#define N 5010
#define mod 100000000
int f[2][N],g[2][N];
char A[N],B[N];
int main()
{
int n,m,i,j,d;
scanf("%s%s",A+1,B+1);
n=strlen(A+1)-1,m=strlen(B+1)-1;
for(i=0;i<=m;i++) f[0][i]=0,g[0][i]=1;
for(d=i=1;i<=n;i++,d^=1)
{
f[d][0]=0,g[d][0]=1;
for(j=1;j<=m;j++)
{
if(f[d^1][j]>f[d][j-1]) f[d][j]=f[d^1][j],
g[d][j]=g[d^1][j];
else if(f[d^1][j]<f[d][j-1])
f[d][j]=f[d][j-1],g[d][j]=g[d][j-1];
else
{
f[d][j]=f[d^1][j],g[d][j]=(g[d^1][j]+g[d][j-1])%mod;
if(f[d][j]==f[d^1][j-1]) g[d][j]=(g[d][j]-g[d^1][j-1]+mod)%mod;
}
if(A[i]==B[j])
{
if(f[d^1][j-1]+1>f[d][j]) f[d][j]=f[d^1][j-1]+1,g[d][j]=g[d^1][j-1];
else if(f[d^1][j-1]+1==f[d][j])
g[d][j]=(g[d][j]+g[d^1][j-1])%mod;
}
}
}
printf("%d\n%d\n",f[n&1][m],g[n&1][m]);
return 0;
}