JZOJ5220. C

题目大意

给出\(A\), \(B\)两个字符串, 求这两个字符串的最长公共子序列在\(B\)中出现的个数.
\(|A|, |B|<=10^3\)

解题思路

看到数据范围,时间复杂度应该是\(O(n^2)\)的.
\(O(n^2)\)求最长公共子序列应该是人尽皆知的.

考虑在这样dp的时候计数. 设\(f_{i,j}\)表示\(A\)串做到\(i\), \(B\)串做到\(j\)时的最长公共子序列, \(g_{i,j}\)表示\(A\)串做到\(i\), \(B\)串做到\(j\)时的公共子序列长度为\(f_{i,j}\)的个数.
\(f_{i,j}\)转移显然. 考虑如何在同时计算\(g_{i,j}\).

把\(g_{i,j}\)分为两个部分来计算以避免算重 : 强制选\(i\)或强制不选\(i\).

1.强制选\(i\)
此时我们选择\(j\)之前的最后一个一个和\(A_i\)相等的位置\(w\)和\(i\)配对.
若满足\(f_{i-1,w-1}+1=f_{i,j}\), 则对\(g_{i,j}\)有\(g_{i-1,w-1}\)的贡献.

讲题时遇到的Q&A:
	Q1:为什么不能选直接选j?  A1:违背了强制选i的限制.
	Q2:为什么选尽量靠后的w?  A2:我们要满足配对以后的序列长度是极长的.并且这样会包含所有的情况.

2.强制不选\(i\)
若满足\(f_{i-1,j}=f_{i,j}\), 则对\(g_{i,j}\)有\(g_{i-1,j}\)的贡献.

最后的答案就是\(g_{|A|,|B|}\). 至于前面的最靠后的字符是容易预处理的.
时间复杂度\(O(n^2)\).

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1010
#define MOD 1000000007
#define fo(i, a, b) for(int i = (a); i <= (b); ++i)
#define fd(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
inline int read() // notice : 1.long long 2.negative
{
	int x = 0; char ch = getchar();
	while(ch < ‘0‘ || ch > ‘9‘)	ch = getchar();
	while(ch >= ‘0‘ && ch <= ‘9‘)	x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return x;
}
int n, m, L, ans, f[N][N], g[N][N], las[N][27];
char s[N], t[N];
int main()
{
//	freopen("string.in", "r", stdin);
//	freopen("string.out", "w", stdout);
	scanf("%s", s + 1); n = strlen(s + 1);
	scanf("%s", t + 1); m = strlen(t + 1);
	fo(i, 1, m)
	{
		fo(j, 0, 25)	las[i][j] = las[i - 1][j];
		las[i][t[i] - ‘a‘] = i;
	}
	fo(i, 1, n)
		fo(j, 1, m)
		{
			f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			s[i] == t[j] && (f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1));
		}
	fo(i, 0, max(n, m))	g[i][0] = g[0][i] = 1;
	fo(i, 1, n)
		fo(j, 1, m)
		{
			if(f[i - 1][j] == f[i][j])	g[i][j] = (g[i][j] + g[i - 1][j]) % MOD;
			int w = las[j][s[i] - ‘a‘];
			if(w && f[i - 1][w - 1] + 1 == f[i][j])	g[i][j] = (g[i][j] + g[i - 1][w - 1]) % MOD;
		}
//	fo(i, 1, n)	fo(j, 1, m)	printf("g[%d][%d] = %d\n", i, j, g[i][j]);
	printf("%d\n", g[n][m]);
	return 0;
}

JZOJ5220. C

原文：https://www.cnblogs.com/Martin-MHT/p/14853269.html