C++で文字列Sに一致する部分列（サブシーケンス）の数を求める方法

文字列 S と単語のリスト words が与えられたとき、S の部分列（サブシーケンス）となっている words[i] の個数を求める問題です。たとえば、入力が S = "abcde"、辞書が ["a", "bb", "acd", "ace"] の場合、出力は 3 になります。これは、辞書の中に「a」「acd」「ace」の3つの単語が S の部分列として含まれているためです（"bb" は 'b' が連続して2つ必要ですが、S 内に 'b' は1つしかないため一致しません）。

解法のアプローチ

この問題は、各単語を「次に照合すべき文字」をキーとしてマップにグループ化し、文字列 S を先頭から1文字ずつ走査しながら待機中の単語を前進させていく手法で効率的に解けます。具体的な手順は以下の通りです。

1. 変数 n に words 配列のサイズを代入します。
2. マップ m を作成します（キー：文字、値：文字列のベクトル）。
3. i を 0 から words のサイズまでループし、各単語 words[i] を m[words[i][0]]（先頭文字をキーとするエントリ）に挿入します。
4. 答えを保持する ans を 0 で初期化します。
5. i を 0 から S のサイズまでループします。
   • 文字 x に S[i] を代入します。
   • x がマップ m に存在する場合は、次の処理を行います。
     • temp に m[x] を取り出し、m[x] を削除します。
     • j を 0 から temp のサイズまでループします。
       • temp[j] のサイズが 1 なら ans を 1 増やします（その単語は完全に一致したことを意味します）。そうでなければ、temp[j] の先頭1文字を除いた部分文字列を m[temp[j][1]] に挿入します。
6. 最後に ans を返します。

C++による実装例

それでは、理解を深めるために実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
  public:
  int numMatchingSubseq(string S, vector<string>& words) {
    int n = words.size();
    map <char, vector <string> > m;
    for(int i = 0; i < words.size(); i++){
      m[words[i][0]].push_back(words[i]);
    }
    int ans = 0;
    for(int i = 0; i < S.size(); i++){
      char x = S[i];
      if(m.find(x) != m.end()){
        vector <string> temp = m[x];
        m.erase(x);
        for(int j = 0; j < temp.size(); j++){
          if(temp[j].size() == 1){
            ans++;
          } else {
            m[temp[j][1]].push_back(temp[j].substr(1));
          }
        }
      }
    }
    return ans;
  }
};
int main() {
  Solution ob1;
  string s = "abcde";
  vector<string> v{"a","bb","acd","ace"};
  cout << ob1.numMatchingSubseq(s, v) << endl;
  return 0;
}

入力

"abcde"
["a","bb","acd","ace"]
string s = "abcde";
vector<string> v{"a","bb","acd","ace"};

出力

3

計算量のポイント

このアルゴリズムでは、文字列 S を一度だけ走査し、各ステップで待機中の単語の「次に必要な文字」だけを更新していきます。そのため、全体の時間計算量は O(|S| + Σ|words[i]|) 程度に抑えられます。各単語ごとに S を最初から走査し直す素朴な方法（O(|S| × 単語数)）と比べて大幅に効率的であり、特に S が長く単語数が多い場合に有効なアプローチです。