C++で別の文字列の部分文字列である1つの文字列の最長部分列の長さを検索します

2つの文字列XとYがあり、文字列Xの最長部分列の長さを見つける必要があるとします。これは、シーケンスYの部分文字列です。したがって、X =“ ABCD”およびY =“ BACDBDCD”の場合、出力は3になります。 。「ACD」はXの最長のサブシーケンスであり、Yのサブストリングです。

ここでは、動的計画法を使用してこの問題を解決します。したがって、Xの長さがnで、Yの長さがmの場合、次数（m + 1）x（n + 1）のDP配列を作成します。 DP [i、j]の値は、X [0…j]のサブシーケンスの最大長であり、Y[0…i]のサブストリングです。これで、DPの各セルについて、次のようになります。

• 1からmの範囲のiの場合：
  • 1からnの範囲のjの場合
    • X [i –1]がY[j – i]と同じ場合、DP [i、j]：=1 + DP [i – 1、j – 1]
    • それ以外の場合、DP [i、j]：=1 + DP [i、j – 1]

そして最後に、yの部分文字列であるxの最長部分列の長さは、max（DP [i、n]）です。ここで、1 <=i<=m。

例

#include<iostream>
#define MAX 100
using namespace std;
int maxSubLength(string x, string y) {
   int table[MAX][MAX];
   int n = x.length();
   int m = y.length();
   for (int i = 0; i <= m; i++)
      for (int j = 0; j <= n; j++)
   table[i][j] = 0;
   for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
         if (x[j - 1] == y[i - 1])
            table[i][j] = 1 + table[i - 1][j - 1];
         else
            table[i][j] = table[i][j - 1];
      }
   }
   int ans = 0;
   for (int i = 1; i <= m; i++)
   ans = max(ans, table[i][n]);
   return ans;
}
int main() {
   string x = "ABCD";
   string y = "BACDBDCD";
   cout << "Length of Maximum subsequence substring is: " << maxSubLength(x, y);
}

出力

Length of Maximum subsequence substring is: 3