JavaScriptで2つの文字列に共通する最長部分文字列を見つける方法

問題の概要

2つの文字列を受け取り、その両方に共通して現れる「最も長い連続した部分文字列」を見つけ出して返すJavaScript関数を作成してみましょう。ここでは、入力文字列を str1 と str2 と呼ぶことにします。

例

たとえば、入力文字列が以下の場合を考えてみます。

const str1 = 'ABABC';
const str2 = 'BABCA';

このとき、期待される出力は次のとおりです。

const output = 'BABC';

解決アプローチ:動的計画法(DP)

この種の問題は動的計画法を使うことで効率的に解くことができます。基本的な考え方は以下のとおりです。

• 2次元の表(arr)を作成し、arr[i][j] には「str2の先頭 i 文字」と「str1の先頭 j 文字」が末尾で一致する共通部分文字列の長さを記録します。
• 比較中の文字が一致していれば、左上のマス(arr[i-1][j-1])の値に1を加えます。一致しなければ 0 をセットします。
• 表全体を走査しながら最大値とその位置を追跡し、最後にその位置から左上方向へ遡ることで、実際の共通部分文字列を復元します。

なお、今回は「連続していること」が条件となるため、文字が一致しなかった時点で値をリセット(0)する点が、一般の最長共通部分列(LCS)問題との大きな違いです。この工夫により、常に連続した部分文字列のみが対象になります。

コード例

以下が実装コードです。

const str1 = 'ABABC';
const str2 = 'BABCA';

const findCommon = (str1 = '', str2 = '') => {
    const s1 = [...str1];
    const s2 = [...str2];
    
    // (s2.length + 1) × (s1.length + 1) の2次元テーブルを作成
    const arr = Array(s2.length + 1).fill(null).map(() => {
        return Array(s1.length + 1).fill(null);
    });
    
    // 最初の行と列を 0 で初期化
    for (let j = 0; j <= s1.length; j += 1) {
        arr[0][j] = 0;
    }
    for (let i = 0; i <= s2.length; i += 1) {
        arr[i][0] = 0;
    }
    
    let len = 0;
    let col = 0;
    let row = 0;
    
    // テーブルを順に埋めていく
    for (let i = 1; i <= s2.length; i += 1) {
        for (let j = 1; j <= s1.length; j += 1) {
            if (s1[j - 1] === s2[i - 1]) {
                arr[i][j] = arr[i - 1][j - 1] + 1;
            }
            else {
                arr[i][j] = 0;
            }
            // 最大値とその位置を記録
            if (arr[i][j] > len) {
                len = arr[i][j];
                col = j;
                row = i;
            }
        }
    }
    
    // 共通部分が存在しない場合
    if (len === 0) {
        return '';
    }
    
    // 最大値の位置から左上へ遡って文字列を復元
    let res = '';
    while (arr[row][col] > 0) {
        res = s1[col - 1] + res;
        row -= 1;
        col -= 1;
    }
    return res;
};

console.log(findCommon(str1, str2));

出力

コンソールには次のように出力されます。

BABC

コードのポイント解説

• 文字列の配列化: スプレッド構文([...str])を使うことで、文字列を1文字ずつの配列として扱いやすくしています。
• テーブルの初期化: 先頭の行・列を 0 にしておくことで、境界条件をシンプルに扱えます。
• len / row / col の追跡: 走査中に現れた最大値とその座標を保持しておくことで、後から復元を開始する位置がわかります。
• 復元処理: 値が 0 より大きい間、左上方向へ1マスずつ移動しながら対応する文字を先頭に連結していきます。

計算量について

このアルゴリズムの時間計算量は O(m × n)(m、n はそれぞれの文字列の長さ)、空間計算量も O(m × n) となります。2重ループでテーブルを一度埋めるだけのシンプルな構造のため、数千文字程度の文字列であれば十分に高速に動作します。ただし、非常に長い文字列を扱う場合はメモリ使用量に留意が必要です。