最长的公共子序列是在给定序列或数组中都存在的一种子序列。
我们可以看到有很多子问题,这些子问题被反复计算以解决这个问题。通过使用动态编程的重叠子结构属性,我们可以克服计算上的麻烦。一旦计算出子问题的结果并将其存储在表中,我们就可以使用先前的结果简单地计算下一个结果。
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