Trình tự con chung dài nhất

Dãy con chung dài nhất là một loại dãy con có trong cả hai dãy hoặc mảng đã cho.

Chúng ta có thể thấy rằng có rất nhiều bài toán con được tính toán lặp đi lặp lại để giải quyết vấn đề này. Bằng cách sử dụng Thuộc tính cấu trúc con chồng chéo của lập trình động, chúng ta có thể vượt qua những nỗ lực tính toán. Sau khi kết quả của các bài toán con được tính toán và lưu trữ trong bảng, chúng ta có thể chỉ cần tính toán các kết quả tiếp theo bằng cách sử dụng các kết quả trước đó.

Đầu vào và Đầu ra

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.

Thuật toán

longestComSubSeq(str1, str2)

Đầu vào - Hai chuỗi để tìm độ dài của Chuỗi con chung dài nhất.

Đầu ra - Chiều dài của 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

Ví dụ

#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);
}

Đầu ra

Length of Longest Common Subsequence is: 4