最長共通部分列

最長共通部分列は、指定されたシーケンスまたは配列の両方に存在するタイプのサブシーケンスです。

この問題を解決するために何度も計算される、多くのサブ問題があることがわかります。動的計画法の重複部分構造プロパティを使用することにより、計算の労力を克服できます。サブ問題の結果が計算されてテーブルに保存されると、前の結果を使用して次の結果を簡単に計算できます。

入力と出力

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)

入力- 最長共通部分列の長さを見つけるための2つの文字列。

出力- 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