C++で最長共通部分列の長さを見つけるプログラム

2つの文字列text1とtext2があるとすると、それらの最も長い共通のサブシーケンスの長さを見つける必要があります。文字列のサブシーケンスは、元の文字列から生成された新しい文字列であり、残りの文字の相対的な順序を変更せずに一部の文字が削除されています。 （たとえば、「abe」は「abcde」のサブシーケンスですが、「adc」はそうではありません）。 2つの文字列の共通のサブシーケンスは、両方の文字列に共通のサブシーケンスです。したがって、共通のサブシーケンスがない場合は0を返します。入力が「abcde」や「ace」の場合、結果は3になります。

これを解決するには、次の手順に従います-

• n：=sのサイズ、m：=xのサイズ

• nが0、またはmが0の場合、0を返します

• s：=空の文字列、sと連結

• x：=空の文字列、xと連結

• ret：=0

• 次数（n + 1）x（m + 1）の行列dpを定義します

• 1からnの範囲のiの場合

  • 1からmの範囲のjの場合

    • dp [i、j]：=dp [i、j-1]およびdp [i – 1、j]

      の最大値

    • s [i] =x [j]の場合、

      • dp [i、j]：=最大dp [i、j]、1 + dp [i – 1、j – 1]

• dp [n、m]

  を返します

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestCommonSubsequence(string s, string x) {
      int n = s.size();
      int m = x.size();
      if(!n || !m) return 0;
      s = " " + s;
      x = " " + x;
      int ret = 0;
      vector < vector <int> > dp(n + 1, vector <int>(m + 1));
      for(int i = 1; i <= n; i++){
         for(int j = 1; j <= m ; j++){
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            if(s[i] == x[j]) {
               dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
            }
         }
      }
      return dp[n][m];
   }
};
main(){
   Solution ob;
   cout << (ob.longestCommonSubsequence("abcde", "ace"));
}

入力

"abcde"
"ace"

出力

3