C++ で最も長い共通部分文字列を見つける

この記事では、C++ での動的プログラミングを使用して、最長の一般的な部分文字列の問題とその解決策について説明します。

最長共通部分文字列

最長共通部分文字列 (LCS) は、コンピューター サイエンスではよく知られている問題です。 2つ以上の文字列の最大長の部分文字列は、最も長い共通部分文字列です。

たとえば、次の 3つの文字列について考えてみます。

1. XYZYZ
2. YXYZX
3. XYZYX

これら 3つの文字列の最長共通部分文字列は XYZ です。 これら 3つの文字列には、X、XY、Y、YX、YZ、Z などの他の一般的な部分文字列が存在します。 ただし、最長の共通部分文字列は XYZ のみです。

図 1 は、上記の 3つの文字列の最長共通部分文字列を示しています。

最長共通部分文字列の問題定式化

それぞれ長さが m と n の 2つの文字列 S1 と S2 を考えて、S1 と S2 の両方から最大長の正確な部分文字列を見つけます。

この問題に対する 2つの解決策を紹介します。

1. シンプルなソリューション
2. 動的計画法ソリューション

シンプルなソリューション

以下は、単純な解決策を使用して 2つの文字列から最長の共通部分文字列を見つける手順です。

このソリューションは、最長の共通部分文字列を見つけることができます。 ただし、時間がかかるため、同じ目標を短時間で達成するための動的計画法ソリューションを見てみましょう。

動的計画法による最長共通部分文字列の検索

動的計画法 (DP) を使用して、2つの文字列から最長共通部分文字列 (LCS) を見つけることができます。 以下は、動的計画法のアプローチを使用して最長の共通部分文字列を見つけるための疑似コードです。

function Longest_Common_Substring(S1[1..m], S2[1..n])
    DP_Matrix = array(1..m, 1..n)
    len = 0
    result_substring = {}
    for i = 1..m
        for j = 1..n
            if S1[i] == S2[j]
                if i = 1 or j = 1
                    DP_Matrix[i, j] = 1
                else
                    DP_Matrix[i, j] = DP_Matrix[i − 1, j − 1] + 1
                if DP_Matrix[i, j] > len
                    len = DP_Matrix[i, j]
                    result_substring = {S1[i − len + 1..i]}
                else if DP_Matrix[i, j] == len
                    result_substring = result_substring ∪ {S1[i − len + 1..i]}
            else
                DP_Matrix[i, j] = 0
    return result_substring

上記の解は、最長の共通部分文字列を計算するのに 2 次 (つまり、$\mathcal{O}(mn)$) の計算量を要します。 ソリューションは最適であり、常に最長のサブマッチを保証します。

注: 疑似コードの配列はインデックス 1 から始まります。さらに、このアルゴリズムは空でない文字列でのみ正常に機能します。

DP_Matrix は、接頭辞 S1[1..i] および S2[1..j] の部分文字列の長さを格納する動的プログラミング テーブルとして使用される 2D 配列または行列であり、終了位置 S1[i] と S2[j].

変数 len は、これまでに見つかった現在の最大 result_substring の長さを格納するために使用されます。 部分文字列は、長さ len の文字列を格納するために使用されます。

DP_matrix の最初の行と列のすべてのセルは 1 に初期化されます。 目的関数を使用して、残りのセルを計算します。

この定式化の目的関数は、次のように表すことができます。

1. 特定のセル DP_Matrix[i,j] について、特定の文字列シーケンスの対応する文字 (つまり、S1[i] と S2[j] の文字) が一致する場合、1 を追加します セル DP_Matrix[i-1,j-1] の値に。
   • セル DP_Matrix[i,j] の更新された値が部分文字列の以前の長さより大きい場合、この新しい値で len を更新します。
   • 同時に、この新しい最大文字列を補助文字列ホルダー (つまり、result_substring) に保存します。
2. 対応する文字が一致しない場合 (つまり、不一致の場合)、セル DP_Matrix[i, j] にゼロ値を設定し、ここから新しい部分文字列のみを開始できることを示します。

すべての M*N 反復 (つまり、for ループの終わり) の後、result_substring には最適な最大の共通部分文字列が含まれます。

C++ での最長共通部分文字列動的プログラミング ソリューション

次のコードは、C++ での動的プログラミングを使用して、文字列から最長の共通部分文字列を見つけるために使用されます。

#include <iostream>
#include <string>
using namespace std;

string Longest_Common_Substring(string Str1, string Str2) {
  string result_substring = "";
  int m = Str1.length();
  int n = Str2.length();
  int DP_Matrix[m + 1][n + 1];
  int len = 0;
  int end = 0;

  for (int i = 0; i <= m; i++) {
    for (int j = 0; j <= n; j++) {
      if (Str1[i] == Str2[j]) {
        if ((i == 0) || (j == 0))
          DP_Matrix[i][j] = 1;
        else
          DP_Matrix[i][j] = 1 + DP_Matrix[i - 1][j - 1];

        if (DP_Matrix[i][j] > len) {
          len = DP_Matrix[i][j];
          int start = i - DP_Matrix[i][j] + 1;
          if (end == start) {
            result_substring.push_back(Str1[i]);
          } else {
            end = start;
            result_substring.clear();
            result_substring.append(Str1.substr(end, (i + 1) - end));
          }
        }
      } else {
        DP_Matrix[i][j] = 0;
      }
    }
  }
  return result_substring;
}

int main() {
  string String1, String2;
  cout << "Enter the first string: ";
  cin >> String1;
  cout << "Enter the second string: ";
  cin >> String2;
  string substring = Longest_Common_Substring(String1, String2);
  cout << "LCS of " << String1 << " and " << String2 << " is " << substring
       << " of Length " << substring.length() << endl;
  return 0;
}

上記のコードには、関数 Longest_Common_Substring が含まれています。この関数は、パラメーターとして 2つの文字列 (つまり、String1 と String2) を受け取り、それらの最適な最大共通部分文字列を返します。 Longest_Common_Substring 関数は、動的計画表法を使用してこの LCS を見つけます。

上記のコードでは、DP_Matrix は、文字列サブペア S1[1..i] と S2[1..j] の現在の最適な部分文字列長を格納する 2D 整数配列です。 result_substring は、疑似コードの説明で説明したように、見つかった最長の部分文字列を格納するために使用されます。

上記のコードのさまざまな文字列ペアの出力を見てみましょう。

出力 1:

Enter the first string: ATGCACATA
Enter the second string: GCAATGCACT
LCS of ATGCACATA and GCAATGCACT is ATGCAC of Length 6

出力 2:

Enter the first string: ABCDDFA
Enter the second string: DCDDACDDF
LCS of ABCDDFA and DCDDACDDF is CDDF of Length 4

理論的または数学的な証明に加えて、上記の出力は、説明した動的計画法ソリューションが最適であることを示唆しています。