最长的公共子序列
最长的公共子序列是在给定序列或数组中都存在的一种子序列。
我们可以看到有很多子问题，这些子问题被反复计算以解决这个问题。通过使用动态编程的重叠子结构属性，我们可以克服计算上的麻烦。一旦计算出子问题的结果并将其存储在表中，我们就可以使用先前的结果简单地计算下一个结果。
输入输出
Input: Two strings with different letters or symbols. string 1: AGGTAB string 2: GXTXAYB Output: The length of the longest common subsequence. Here it is 4. AGGTAB and GXTXAYB. The underlined letters are present in both strings and in correct sequence.
算法
longestComSubSeq(str1, str2)
输入- 两个字符串以找到最长公共子序列的长度。
输出-LCS的长度。
Begin
m := length of str1
n := length of str2
define longSubSeq matrix of order (m+1) x (n+1)
for i := 0 to m, do
for j := 0 to n, do
if i = 0 or j = 0, then
longSubSeq[i,j] := 0
else if str1[i-1] = str2[j-1], then
longSubSeq[i,j] := longSubSeq[i-1,j-1] + 1
else
longSubSeq[i,j] := maximum of longSubSeq[i-1, j] and
longSubSeq[i, j-1]
done
done
longSubSeq[m, n]
End示例
#include<iostream>
using namespace std;
int max(int a, int b) {
return (a > b)? a : b;
}
int longestComSs( string str1, string str2) {
int m = str1.size();
int n = str2.size();
int longSubSeq[m+1][n+1];
//longSubSeq[i,j] will hold the LCS of str1 (0 to i-1) and str2 (0 to j-1)
for (int i=0; i<=m; i++) {
for (int j=0; j<=n; j++) {
if (i == 0 || j == 0)
longSubSeq[i][j] = 0;
else if (str1[i-1] == str2[j-1])
longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1;
else
longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1]);
}
}
return longSubSeq[m][n];
}
int main() {
string str1 = "AGGTAB";
string str2 = "GXTXAYB";
cout << "Length of Longest Common Subsequence is: " << longestComSs( str1, str2);
}输出结果
Length of Longest Common Subsequence is: 4