C++で単語リストの全単語を連結した文字列の部分文字列の開始インデックスを検索する方法

問題の概要

文字列 s と、同じ長さの複数の単語を含むリスト words が与えられます。このとき、words 内の各単語をちょうど1回ずつ使用し、間に余計な文字を挟まずに連結してできる部分文字列が、s の中に出現する開始インデックスをすべて求めるのが目的です。

たとえば、入力が "wordgoodgoodgoodword"、単語リストが ["word", "good"] の場合、出力は [0, 12] になります。これは、インデックス 0 から始まる部分文字列が "wordgood"、インデックス 12 から始まる部分文字列が "goodword" であり、どちらも条件を満たすためです。

解法のアプローチ

この問題は、スライディングウィンドウとハッシュマップ（単語の出現回数カウント）を組み合わせることで効率的に解けます。全体の流れは以下の通りです。

補助関数 ok() の定義

まず、ある部分文字列が条件を満たしているかどうかを判定する補助関数 ok() を定義します。引数は文字列 s、単語の出現回数を格納するマップ wordCnt、各単語の長さ n です。

1. s の先頭 n 文字を temp にコピーします。
2. i が n から s のサイズ − 1 までの範囲でループします。
3. temp のサイズが n の倍数であるとき：
   • temp が wordCnt に存在しない場合は false を返します。
   • 存在する場合は、wordCnt[temp] が 1 なら wordCnt から temp を削除し、そうでなければ wordCnt[temp] を 1 減らします。いずれの場合も temp を空文字列にリセットします。
4. temp に s[i] を追加します。
5. ループ終了後も同様に、残った temp が wordCnt に存在しなければ false を返し、存在すれば削除またはカウント減算を行います。
6. 最後に wordCnt のサイズが 0（すべての単語を消費し切った）であれば true を返します。

メイン処理 findSubstring() の流れ

1. 文字列 a または単語リスト b のサイズが 0 の場合は空の配列を返します。
2. マップ wordCnt を作成し、b に含まれる各単語の出現頻度を記録します。
3. 結果を格納する配列 ans を用意します。
4. window ＝ 単語数 × 各単語の文字数 としてウィンドウ幅を計算します。
5. 文字列 a の先頭 window 文字分を temp にコピーします。
6. i が window から a のサイズ − 1 までの範囲でループします。
   • temp のサイズが window の倍数であり、ok(temp, wordCnt, b[0] のサイズ) が true を返す場合は、i − window を ans に追加します。
   • temp に a[i] を追加し、temp のサイズが window を超えたら先頭の 1 文字を削除します。
7. ループ後、temp のサイズが window の倍数かつ ok() が true なら、a のサイズ − window を ans に追加します。
8. ans を返します。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    bool ok(string s, unordered_map <string, int> wordCnt, int n){
        string temp = "";
        for(int i = 0; i < n; i++){
            temp += s[i];
        }
        for(int i = n; i < s.size(); i++){
            if(temp.size() % n == 0){
                if(wordCnt.find(temp) == wordCnt.end())return false;
                else{
                    if(wordCnt[temp] == 1){
                        wordCnt.erase(temp);
                        temp = "";
                    } else {
                        wordCnt[temp]--;
                        temp = "";
                    }
                }
            }
            temp += s[i];
        }
    if(wordCnt.find(temp) == wordCnt.end())return false;
    else{
        if(wordCnt[temp] == 1){
            wordCnt.erase(temp);
            temp = "";
        } else {
            wordCnt[temp]--;
            temp = "";
        }
    }
    return wordCnt.size() == 0;
}
vector<int>findSubstring(string a, vector<string> &b) {
    if(a.size() == 0 || b.size() == 0)return {};
        unordered_map <string, int> wordCnt;
    for(int i = 0; i < b.size(); i++)wordCnt[b[i]]++;
        vector <int> ans;
        int window = b.size() * b[0].size();
        string temp ="";
        for(int i = 0; i < window; i++)temp += a[i];
        for(int i = window; i < a.size(); i++){
            if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())){
                ans.push_back(i - window);
            }
            temp += a[i];
            if(temp.size() > window)temp.erase(0, 1);
        }
        if(temp .size() % window ==0 && ok(temp, wordCnt, b[0].size()))ans.push_back(a.size() - window);
            return ans;
    }
};
main(){
    vector<string> v = {"word","good"};
    Solution ob;
    print_vector(ob.findSubstring("wordgoodgoodgoodword", v));
}

入力

"wordgoodgoodgoodword", {"word","good"}

出力

[0, 12]

まとめ

このアルゴリズムでは、ハッシュマップによる単語カウント管理とスライディングウィンドウを組み合わせることで、すべての候補位置を効率的にチェックできます。計算量はおおよそ O(N × M)（N は文字列の長さ、M は単語数 × 単語長）となり、素朴な全探索アプローチよりも大幅に高速に動作します。重複する単語や繰り返しパターンを含む入力にも正しく対応できる点がポイントです。