目录
- 最长公共子序列
- 问题描述
- 代码实现
- 输出结果
- 注意事项
- 小结:
最长公共子序列
最长公共子序列(Longest Common Subsequence, LCS)问题是计算给定两个序列的最长子序列的长度,这个子序列不要求连续,但需要保持相同的相对顺序。LCS广泛应用于文本比较、DNA序列分析等领域。
问题描述
给定两个字符串,LCS的目标是找出它们之间的最长子序列。对于字符串 x
和 y
,子序列是从 x
或 y
中删除一些字符后得到的新序列,并且删除的字符的相对顺序保持不变。比如,对于字符串 x = "abcde"
和 y = "ace"
,它们的LCS是 "ace"
,长度为3。
该问题可以使用动态规划的方法高效地解决。我们通过构建一个二维数组来存储子问题的解,从而避免重复计算。
代码实现
#include <iostream>
#define M 5
#define N 3
using namespace std;
// 递推求最优值
void LCSLength(int m, int n, char *x, char *y, int c[][N+1], int b[][N+1]){
/*
m:长度 x:字符串
n:长度 y:字符串
c:最优值
b:最优解
*/
// 初始化
for (int i=1; i<= m; i++) c[i][0] = 0;
for (int j=1; j<= n; j++) c[0][j] = 0;
for (int i=1; i<=m; i++){
for (int j=1; j<=n; j++){
if (x[i] == y[j]){
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else if(c[i-1][j] >= c[i][j-1]){
c[i][j] = c[i-1][j];
b[i][j] = 2;
}
else {
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
}
// 递归构建最优解
void LCS(int i, int j, char *x, int b[][N+1]) {
// 终止条件
if (i == 0 || j == 0) return;
// 递归
if (b[i][j] == 1){
LCS(i-1, j-1, x, b);
cout << x[i];
}
else if (b[i][j] == 2){
LCS(i-1, j, x, b);
}
else{
LCS(i, j-1, x, b);
}
}
int main() {
char x[M+1] = {'0', 'a', 'b', 'c', 'd', 'e'};
char y[N+1] = {'0', 'a', 'c', 'e'};
int c[M+1][N+1], b[M+1][N+1];
// 最优值
LCSLength(M, N, x, y, c, b);
// 最优解
LCS(M, N, x, b);
}
输出结果
运行上述代码后,将输出两个字符串的最长公共子序列。对于 x = “abcde” 和 y = “ace”,输出将为:
注意事项
在实现LCS算法时,要注意数组索引的正确性,尤其是在处理字符数组时,确保访问正确的字符。
对于输入字符串的长度,可以根据实际需求调整常量 M 和 N,以适应不同长度的字符串。
动态规划算法的时间复杂度为O(mn),空间复杂度也为O(mn),在处理大字符串时要考虑其性能影响。
标签:LCS,int,字符串,算法,序列,长度,最长 From: https://blog.51cto.com/u_16672541/12100849