C++で連結語（Concatenated Words）をすべて見つけるアルゴリズム

問題の概要

互いに異なる単語からなるリストが与えられたとします。ここで求めたいのは、リストの中に含まれる連結語をすべて見つけるアルゴリズムです。連結語とは、同じリスト内にある少なくとも2つの短い単語を組み合わせて完全に構成できる文字列のことを指します。

たとえば、単語リストが ["cow", "cows", "cowsgoatcows", "goat", "goatcowsgoat", "hippopotamuses", "deer", "deercowgoatcow"] である場合、出力は ["cowsgoatcows", "goatcowsgoat", "deercowgoatcow"] となります。

解き方のアプローチ

この問題は、トライ木（Trie）とメモ化再帰（動的計画法）を組み合わせることで効率よく解くことができます。基本的な考え方は次のとおりです。

1. 単語を長さの昇順にソートします。
2. 短い単語から順に処理し、まだトライ木に登録されていない単語について、それより前に登録済みの単語だけで分割できるかを判定します。
3. 分割できれば連結語として結果に追加し、できなければその単語をトライ木に新しく登録します。

この順序で処理することで、ある単語をチェックする時点では必ず「それより短い単語のみ」がトライ木に存在することになり、自分自身を1つの単語として使う不正な分割を自然に防ぐことができます。

isPresent() 関数：文字列が分割可能かを判定

関数 isPresent() は、対象文字列 str、トライ木のルート head、現在位置 idx、メモ化用配列 dp を受け取ります。

• idx が str の長さ以上になったら true を返します（末尾まで到達＝分割成功）。
• dp[idx] が -1 以外なら、すでに計算済みなのでその値を返します。
• ノード curr を head で初期化し、フラグ ok を false にします。
• i を idx から文字列の末尾まで進めながら、次を繰り返します。
  • x := str[i]
  • curr に子ノード child[x] が存在しなければ、ループを抜けます。
  • 存在すれば curr := child[x] とします。
  • curr の isEnd が true（そこまでが1つの単語）であれば、ok := ok OR isPresent(str, head, i + 1, dp) で残りの部分を再帰的に判定します。
• 最後に dp[idx] := ok をメモして返します。

insertNode() 関数：トライ木への単語登録

関数 insertNode() は、ルート head と文字列 s を受け取り、s をトライ木に挿入します。各文字に対応する子ノードが存在しない場合は新規ノードを作成し、最後のノードの isEnd を true に設定します。

メインメソッドの流れ

1. 新しいノードを作成してルート head とします。
2. 単語配列 words を長さ順にソートします。
3. 結果格納用の配列 ret を用意します。
4. 各単語 curr に対して次を処理します。
   • curr が空文字列ならスキップします。
   • curr と同じサイズの dp 配列を作成し、すべて -1 で初期化します。
   • isPresent(curr, head, 0, dp) が真であれば、curr を ret の末尾に追加します。
   • そうでなければ insertNode(head, curr) を呼び出してトライ木に登録します。
5. ret を返します。

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;
}
struct Node{
    bool isEnd;
    map <char, Node*> child;
    Node(){
        isEnd = false;
    }
};
class Solution {
public:
    bool isPresent(string str, Node* head, int idx, vector <int>& dp){
        if(idx >= str.size())return true;
        if(dp[idx] != -1)return dp[idx];
        Node* curr = head;
        bool ok = false;
        for(int i = idx; i < str.size(); i++){
            char x = str[i];
            if(!curr->child[x]){
                break;
            }else{
                curr = curr->child[x];
            }
            if(curr->isEnd){
                ok |= isPresent(str, head, i + 1, dp);
            }
        }
        return dp[idx] = ok;
    }
    static bool cmp(string s1, string s2){
        return s1.size() < s2.size();
    }
    void insertNode(Node* head, string s){
        Node* curr = head;
        for(int i = 0; i < s.size(); i++){
            char x = s[i];
            if(!curr->child[x]){
                curr->child[x] = new Node();
            }
            curr = curr->child[x];
        }
        curr->isEnd = true;
    }
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        Node* head = new Node();
        sort(words.begin(), words.end(), cmp);
        vector <string> ret;
        for(int i = 0; i < words.size(); i++){
            string curr = words[i];
            if(curr=="")continue;
            vector <int> dp(curr.size(), -1);
            if(isPresent(curr, head, 0, dp)){
                ret.push_back(curr);
            }else{
                insertNode(head, curr);
            }
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<string> v =    {"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"};
    print_vector(ob.findAllConcatenatedWordsInADict(v));
}

入力

{"cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"}

出力

[cowsgoatcows, goatcowsgoat, deercowgoatcow]

計算量について

各単語の分割判定では、開始位置ごとにトライ木を辿るため O(L²)（L は単語の長さ）、単語数を N とすると全体で O(N・L²) 程度の時間計算量になります。メモ化によって同じ開始位置の再計算が回避されるため、素朴な全探索に比べて大幅に高速に動作します。