最长公共子序列（LCS）及其应用（密码脱落）_最长公共子序列的应用

最长公共子序列（LCS）及其应用（密码脱落）

给定两个 string 字符串，找出他们的最长公共子序列（Longest Common Sequence，LCS）。

例如 string A = “BDCABA“，string B = ”ABCBDAB“，他们的LCS = 4。

求最长公共子序列的经典方法属于一种动态规划（Dynamic Programming，DP）。

而动态规划的两个基本要素为：① 最优子结构 ② 重叠子问题

① 最优子结构

设 X = x₁ x₂ … x_n Y = y₁ y₂ … y_m

若 x_n == y_m，说明该元素一定存在于LCS中，

故只要求 LCS（X_n-1，y_m-1），这是一个最优的子问题。

若 x_n != y_m，则继续分类缩小问题的范围。

故只要求 max{LCS(X_n-1，Y_m)，LCS(X_n，Y_m-1)} 即可。

② 重复子问题

LCS（X，Y）：LCS（X_n-1，Y_m-1），LCS（X_n-1，Y_m），LCS（X_n，Y_m-1）

LCS（X_n-1，Y_m）：LCS（X_n-2，Y_m-1），LCS（X_n-2，Y_m），LCS（X_n-1，Y_m-1）

……

如图会有很多重复的子问题，若用递归做时间会以指数增长。

用 dp 做的直接进行“查表”即可。

综上：

参考代码：

int LCS(string str1, string str2){
	// 初始化第一行和第一列 
	for(int i = 0; i <= len1; i++){
		dp[i][0] = 0;
	}
	for(int i = 0; i <= len2; i++){
		dp[0][i] = 0;
	}
	// 构建dp数组 
	for(int i = 1; i <= len1; i++){
		for(int j = 1; j <= len2; j++){
			if(str1[i] == str2[j]){  // 如果该位置上的字符相同 dp值 = 没有当前字符时的LCS值+1 
				dp[i][j] = dp[i-1][j-1]+1;
			}
			else{  // 如果不同 dp值 = 单字符串去掉当前字符时的两个LCS中的最大值 
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}
	return dp[len1][len2];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

关于LCS的应用——密码脱落：

问题描述如下：

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

输入一行，表示现在看到的密码串（长度不大于1000）
要求输出一个正整数，表示至少脱落了多少个种子。

例如，输入：
ABCBA
则程序应该输出：
0

再例如，输入：
ABECDCBABC
则程序应该输出：
3

也就是说至少需要添加多少个字符才可以变成一个镜像串。

怎么联系到最长公共子序列呢？

因为原本是一个镜像串，镜像串的特点就是正序和逆序相同。

我们可以利用这一点，把脱落后的密码串进行反转，再跟反转前的密码串进行比对。

找到最长的公共子序列之后，其余剩下没有匹配成功的字符就是需要添加的字符。

这样就可以保证添加最少的字符来还原一个镜像串。

参考代码如下：

// 第七届蓝桥杯第九题 
#include<iostream>
using namespace std;

int **arr;

// 翻转 
string reverse(string str){
	string sub = str;
	for(int i = 0; i < sub.length()/2; i++){
		char ch = sub[i];
		sub[i] = sub[sub.length()-1-i];
		sub[sub.length()-1-i] = ch; 
	}
	return sub;
}

// 求最长公共子序列 
int getLCS(string str1, string str2){
	// 动态创建二维数组 
	arr = new int*[str1.length()+1];
	for(int i = 0; i <= str1.length(); i++){
		arr[i] = new int[str2.length()+1];
	}
	// 将第一行和第一列初始化为0 
	for(int i = 0; i <= str1.length(); i++){
		arr[i][0] = 0;
	}
	for(int i = 0; i <= str2.length(); i++){
		arr[0][i] = 0;
	}
	// 根据公式计算二维数组 
	for(int i = 1; i <= str1.length(); i++){
		for(int j = 1; j <= str2.length(); j++){
			if(str1[i] == str2[j]){
				arr[i][j] = arr[i-1][j-1]+1;
			}
			else if(arr[i-1][j] > arr[i][j-1]){
				arr[i][j] = arr[i-1][j];
			}
			else{
				arr[i][j] = arr[i][j-1];
			}
		}
	}
	// 返回两个字符串的LCS 
	return arr[str1.length()][str2.length()];
}

int main(){
	string str;
	while(cin >> str){
		string sub = reverse(str);
		int len = getLCS(str, sub);
		// 用原长减去LCS就是答案 
		cout << str.length()-len << endl; 
		for(int i = 0; i < str.length()+1; i++){
			delete []arr[i];
		}
		delete []arr;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

【END】感谢观看