[题解]P2516 [HAOI2010] 最长公共子序列——求LCS个数

P2516 [HAOI2010] 最长公共子序列

总的来说，这道题确实很精妙，难度也不小，耗费了不少时间去调。本来想过用容斥的思想，却因为当时理解不深没有继续思考就放弃了。学会了思路后对\(LCS\)有了更深层次的理解。

题意简述

给定\(A,B\)两个字符串（以.结尾），求它们的最长公共子序列的长度和个数（取模\(10^8\)）。

注意：两个字符串可能有多个最长公共子序列，同一个最长公共子序列，哪怕放的位置不同，也算作两个。

样例

输入：

ABCBDAB.
BACBBD.

输出：

4
7

样例解释

长度为\(4\)：ABBD\(*1\)，ACBB\(*1\)，ACBD\(*2\)，BCBB\(*1\)，BCBD\(*2\)。

思路简述

根据\(LCS\)算法的思想，我们画出以下表格（注意路径不唯一，所以每个格子不止一个箭头）。右下角的暗红色数字是\(f\)数组，记录长度。

第一问就是\(f[n][m]\)的值（\(n,m\)表示\(A,B\)的长度）。

第二问怎么解决呢？结果显然就是从\((n,m)\)开始，根据格子上的指示回溯的路径条数。当时以为这里用记忆化搜索直接计数就能得到正确答案，但其实这样做可能会有重复。如下图：

从右下开始走，左-上-左上和上-左-左上的效果是一样的，都是选择了C加入子序列。而左上-左上的效果不同，选择了D和C加入子序列。由此可以看出并不是路径不同最终子序列就不同。应该是路径中经过↖的位置不同，最终子序列就不同（注意不同的子序列可能字符串表示相同，前面题意简述说明了）。

所以搜索的方法会有重复计算的错误，考虑和\(f\)一样，定义一个\(g\)数组，\(g[i][j]\)表示\(A,B\)长度分别为\(i,j\)的前缀\(LCS\)的个数。

• 如果\(a[i]=b[j]\)，说明此处有一个↖，那么应该有这样子\(4\)种情况：
  
  也就是说，如果\(a[i]=b[j]\)，首先\(g[i][j]+=g[i-1][j-1]\)，表示从这个格子往↖走的个数（长度为\(3+1=4\)），如果\(f[i-1][j]=f[i][j]\)或者\(f[i][j-1]=f[i][j]\)，说明我们也可以不选↖，而是选择←或↑，仍然能选\(4\)个。

• 如果\(a[i]\neq b[j]\)，那么此处没有↖。判断方法相同：

  • 如果\(f[i-1][j]=f[i][j]\)说明有↑，\(g[i][j]+=g[i-1][j]\)；
  • 如果\(f[i][j-1]=f[i][j]\)说明有←，\(g[i][j]+=g[i][j-1]\)。

  但是如果\(f[i-1][j-1]=f[i][j]\)（\(a[i]\neq b[j]\)不代表\(f[i-1][j-1]\neq f[i][j]\)），说明左-和上-的操作可能有重复计算（就是第二张图那种，左-上和上-左都能到达\((i-1,j-1)\)，又因为\(f[i-1][j-1]=f[i][j]\)，所以都是最长。这样就重复计算了），需要\(g[i][j]-=g[i-1][j-1]\)。

综上，我们得到状态转移方程：

\(f[i][j]= \begin{cases} f[i-1][j-1]+1 & if\ a[i]=b[j]\\ max(f[i-1][j],f[i][j-1]) & otherwise \end{cases}\)

\(g[i][j] \begin{cases} =1 & if\ i=0\ or\ j=0\\ otherwise:\\ +=g[i-1][j-1] & if\ a[i]=b[j]\\ +=g[i-1][j] & if\ f[i-1][j]=f[i][j]\\ +=g[i][j-1] & if\ f[i][j-1]=f[i][j]\\ -=g[i-1][j-1] & if\ f[i-1][j-1]=f[i][j]\\ \end{cases}\)

注意事项

• 别忘取模\(10^8\)。
• 开\(5000*5000\)会炸空间，所以需要滚动数组优化空间。
• 虽然递推有减法，但我们不需要担心出现负数影响取模。因为我们一定会作加法，而且加的数所在位置一定不在减的数所在位置左或上（还是比较容易理解的）。

具体见代码~

Code

#include<bits/stdc++.h>
#define int long long
#define mod 100000000ll
using namespace std;
string a,b;
int n,m,f[5010][5010];
int g[5010][5010];
signed main(){
	cin>>a>>b;
	n=a.size()-1,m=b.size()-1;
	a=' '+a,b=' '+b;
	bool cur=1,pre=0;
	for(int i=0;i<=m;i++) g[0][i]=1;
	g[1][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			g[cur][j]=0;
			if(a[i]==b[j]) f[cur][j]=f[pre][j-1]+1;
			else f[cur][j]=max(f[pre][j],f[cur][j-1]);
			if(a[i]==b[j]) g[cur][j]+=g[pre][j-1];
			if(f[cur][j]==f[cur][j-1]) g[cur][j]+=g[cur][j-1];
			if(f[cur][j]==f[pre][j]) g[cur][j]+=g[pre][j];
			if(f[cur][j]==f[pre][j-1]) g[cur][j]-=g[pre][j-1];
			g[cur][j]%=mod;
		}
		cur=!cur,pre=!pre;
	}
	cout<<f[pre][m]<<endl<<g[pre][m];
	return 0;
}

欢迎在评论区留下你的问题或建议。