C++で最長共通部分文字列の長さを求めるプログラム

2つの小文字からなる文字列 X と Y が与えられたとき、両方の文字列に共通して現れる部分文字列の中で最も長いもの（最長共通部分文字列）の長さを求めます。

例えば、X = "helloworld"、Y = "worldbook" という入力の場合、最も長い共通部分文字列は "world" であり、その長さは 5 となるため、出力は 5 になります。

この問題は動的計画法（DP）を使うことで効率的に解くことができます。各位置で文字が一致した場合に、左上のセルの値に1を加えていくことで、連続する一致の長さを記録していきます。

アルゴリズムの手順

• (m+1) × (n+1) のサイズを持つ2次元配列 longest を定義します。
• len := 0 で初期化します。
• i を 0 から m までループします。
  • j を 0 から n までループします。
    • i が 0 または j が 0 の場合：
      longest[i][j] := 0
    • X[i-1] と Y[j-1] が等しい場合：
      longest[i][j] := longest[i-1][j-1] + 1
      さらに len < longest[i][j] であれば、len、row、col を更新します。
    • 上記以外の場合：
      longest[i][j] := 0
• 最後に len を返します。

それでは、実際の実装を見てみましょう。

C++での実装例

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
int solve(char* X, char* Y, int m, int n){
    int longest[m + 1][n + 1];
    int len = 0;
    int row, col;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                longest[i][j] = 0;
            else if (X[i - 1] == Y[j - 1]) {
                longest[i][j] = longest[i - 1][j - 1] + 1;
                if (len < longest[i][j]) {
                    len = longest[i][j];
                    row = i;
                    col = j;
                }
            }
            else
                longest[i][j] = 0;
        }
    }
    return len;
}
int main(){
    char X[] = "helloworld";
    char Y[] = "worldbook";
    int m = strlen(X);
    int n = strlen(Y);
    cout << solve(X, Y, m, n);
    return 0;
}

入力

"helloworld", "worldbook"

出力

5

計算量について

このアルゴリズムの時間計算量は O(m × n)、空間計算量も O(m × n) です。2次元テーブルを使用しているためメモリ消費はやや大きくなりますが、ブルートフォース（全探索）の O(m × n × min(m, n)) と比較すると大幅に高速です。なお、変数 row と col は最大長の部分文字列が終了する位置を記録しており、実際に部分文字列そのものを取得したい場合は、X の row-len 番目から len 文字を切り出すことで求めることができます。