JavaScriptで一致する部分文字列（部分列）の数を効率的に数える方法

問題

JavaScriptで、第1引数に文字列 str、第2引数に文字列の配列 arr を受け取る関数を作成します。この関数は、配列内の各要素 arr[i] のうち、文字列 str の「部分列」となっているものの個数を数えて返す必要があります。

ここでの「部分列」とは、元の文字列から0個以上の文字を削除して得られる文字列であり、必ずしも連続している必要はない点に注意してください。これは「部分文字列」とは異なる概念です。

例として、次のような入力が与えられた場合を考えてみましょう。

入力

const str = 'klmnop';
const arr = ['k', 'll', 'klp', 'klo'];

出力

const output = 3;

出力の解説

'k'、'klp'、'klo' の3つは str='klmnop' の部分列として成立します。一方 'll' は 'l' が1つしか存在しないため部分列にはなりません。したがって答えは 3 となります。

アプローチ：マップを使った効率的な走査

各候補文字列に対して毎回 str を走査すると計算量が大きくなりますが、str を一度だけ左から右へスキャンし、各単語の「どこまで照合できたか」を管理することで効率化できます。

具体的には以下の手順で処理します。

1. まず、配列の各単語について「先頭の文字」をキーとするマップを作成します。値は [単語のインデックス, 照合済み文字数] のペアのリストです。
2. str を先頭から1文字ずつ見ていき、現在の文字がマップのキーとして存在すれば、そのリストに含まれるすべてのエントリを取り出します。
3. エントリごとに、その単語の最後の文字まで照合が完了していればカウントを +1 し、そうでなければ次の文字をキーとしてマップに再登録します。
4. 同じ文字位置で複数回登録されないよう、キーを一時的に undefined にして重複を防ぎます。

これにより、時間計算量は str の長さと全単語の総文字数に比例する形になり、総当たり的な比較より大幅に高速化されます。

コード例

以下が実際のコードです。

const str = 'klmnop';
const arr = ['k', 'll', 'klp', 'klo'];

const countSubstrings = (str = '', arr = []) => {
  // 各単語の先頭文字をキーに、[単語番号, 照合済み文字数] を登録
  const map = arr.reduce((acc, val, ind) => {
    const c = val[0];
    acc[c] = acc[c] || [];
    acc[c].push([ind, 0]);
    return acc;
  }, {});

  let num = 0;

  // str を1文字ずつ走査
  for (let i = 0; i < str.length; i++) {
    if (map[str[i]] !== undefined) {
      const list = map[str[i]];
      map[str[i]] = undefined; // 同じ位置での重複処理を防止

      list.forEach(([wordIndex, charIndex]) => {
        if (charIndex === arr[wordIndex].length - 1) {
          // 最後の文字まで一致したのでカウント
          num += 1;
        } else {
          // 次に必要な文字をキーとして再登録
          const nextChar = arr[wordIndex][charIndex + 1];
          map[nextChar] = map[nextChar] || [];
          map[nextChar].push([wordIndex, charIndex + 1]);
        }
      });
    }
  }

  return num;
};

console.log(countSubstrings(str, arr));

出力結果

3

まとめ

この手法では、str を1回だけ走査しながら、すべての候補単語の照合状況をマップで並行管理できます。単純に各単語ごとに二重ループで判定する方法（O(n×m×k)）と比べ、大規模な入力でもパフォーマンスが安定するのが大きな利点です。部分列マッチングの問題は LeetCode の「Number of Matching Subsequences」などでも頻出のテーマなので、この実装パターンは覚えておくと役立ちます。