最长公共子序列

最长公共子序列

Longest Common Subsequence

区分 子序列 子串
子序列可以不连续
子串必须连续

LCS of S and T

f[i][j] = LCS of S[1..i] and T[1..j]

for (int i = 1; i <= s.size(); i++)
{
    for (int j = 1; j <= t.size(); j++)
    {
        if (s[i-1] == t[j-1]) // 注意 s 和 t 下标从 0 开始 还是 从 1 开始
        {
            f[i][j] = f[i-1][j-1] + 1;
        }
        else
        {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
        }
    }
}

最长公共子序列 转 最长不下降子序列

5
3 2 1 4 5
1 2 3 4 5

c b a d e
a b c d e

1 2 3 4 5
3 2 1 4 5

注意到 第二个排列的 任意一个
上升子序列 一定是一个 公共子序列
一定一一对应

所以说第二个 最长上升子序列的长度 == 最长公共子序列的长度

P2758 编辑距离

https://www.luogu.com.cn/problem/P2758

题目描述

设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

$A, B$ 均只包含小写字母。

输入格式

第一行为字符串 $A$；第二行为字符串 $B$；字符串 $A, B$ 的长度均小于 $2000$。

输出格式

只有一个正整数，为最少字符操作次数。

样例 #1

样例输入 #1

sfdqxbw
gfdgw

样例输出 #1

4

提示

对于 $100 \%$ 的数据，$1 \le |A|, |B| \le 2000$。

参考代码

#include <bits/stdc++.h>
using namespace std;
char a[2020], b[2020];
int f[2020][2020];
int n, m;
int main() {
	scanf("%s%s", a + 1, b + 1);
	n = strlen(a + 1);
	m = strlen(b + 1);
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (i == 0 || j == 0) {
				f[i][j] = i + j;
			} else if (a[i] == b[j]) {
				f[i][j] = f[i - 1][j - 1];
			} else {
				f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
			}
		}
	}
	printf("%d\n", f[n][m]);
	return 0;
}

题解

f[i][j] 表示第一个序列的前i个，和第二个序列的前j个，的最优解

A串的前i个字符 改成 B串的前j个字符 最小代价

在A字符串中加入字符 等价于 在B字符串中删除字符
在A字符串中删除字符 等价于 在B字符串中加入字符
在A字符串中修改字符 等价于 在B字符串中修改字符

The min cost to change A[1..i] to B[1..j]

f[i][j] = min(f[i-1][j-1] + change cost, f[i][j-1] + insert cost, f[i-1][j] + delete cost)
change cost = A[i] == B[j] ? 0 : 1;

P1279 字串距离

https://www.luogu.com.cn/problem/P1279

题目描述

设有字符串 $X$，我们称在 $X$ 的头尾及中间插入任意多个空格后构成的新字符串为 $X$ 的扩展串，如字符串 $X$ 为abcbcd，则字符串abcb□cd，□a□bcbcd□和abcb□cd□ 都是 $X$ 的扩展串，这里□代表空格字符。

如果 $A_1$ 是字符串 $A$ 的扩展串，$B_1$ 是字符串 $B$ 的扩展串，$A_1$ 与 $B_1$ 具有相同的长度，那么我们定义字符串 $A_1$ 与 $B_1$ 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为 $0$。在字符串 $A$、$B$ 的所有扩展串中，必定存在两个等长的扩展串 $A_1$，$B_1$，使得 $A_1$ 与 $B_1$ 之间的距离达到最小，我们将这一距离定义为字符串 $A$，$B$ 的距离。

请你写一个程序，求出字符串 $A$，$B$ 的距离。

输入格式

输入文件第一行为字符串 $A$ ，第二行为字符串 $B$。$A$，$B$ 均由小写字母组成且长度均不超过 $2000$。第三行为一个整数 $K(1\leq K\leq 100)$，表示空格与其他字符的距离。

输出格式

输出文件仅一行包含一个整数，表示所求得字符串 $A,B$ 的距离。

样例 #1

样例输入 #1

cmc
snmn
2

样例输出 #1

10

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
char a[2020], b[2020];
int f[2020][2020];
int n, m, k;
int main() {
	scanf("%s%s%d", a + 1, b + 1, &k);
	n = strlen(a + 1);
	m = strlen(b + 1);
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (i == 0 || j == 0) {
				f[i][j] = (i + j) * k;
			} else {
				f[i][j] = min(f[i - 1][j - 1] + abs(a[i] - b[j]), min(f[i - 1][j], f[i][j - 1]) + k);
			}
		}
	}
	printf("%d\n", f[n][m]);
	return 0;
}

题解

f[i][j] 表示第一个序列的前i个，和第二个序列的前j个，的最优解

样例

 c mc 
s nm n

m和m对应了，有5个位置是字符匹配空格，总距离是5 * 2 = 10

f[i][j] 表示A串的前i个字符 改成 B串的前j个字符 的最小代价

The min cost to change A[1..i] to B[1..j]
f[i][j] = min(f[i-1][j-1] + abs(a[i] - b[j]), f[i][j-1] + K, f[i-1][j] + K)

abc185_e Sequence Matching

https://atcoder.jp/contests/abc185/tasks/abc185_e

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1020];
int b[1020];
int f[1020][1020];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d", &b[i]);
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (i == 0 || j == 0) {
				f[i][j] = i + j;
			} else if (a[i] == b[j]) {
				f[i][j] = f[i - 1][j - 1];
			} else {
				f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
			}
		}
	}
	printf("%d\n", f[n][m]);
	return 0;
}

题解

编辑距离