C++で辞書から特定のパターンに一致するすべての文字列を検索する方法

文字列のリスト（辞書）とパターン文字列が与えられ、そのパターンに一致する文字列を辞書からすべて見つける問題を考えてみましょう。例えば、辞書が ["abb", "xyz", "aab", "kmm"]、パターンが "stt" である場合、結果は "abb" と "kmm" となります。これは、パターンが「最初に1文字、続いて同じ2文字」という構造を持っているため、同じ構造を持つ文字列だけが該当するからです。

解決のアプローチ

この問題を効率的に解くには、パターンをエンコードします。エンコードの際、パターンに一致する辞書内の単語は、パターンと同じハッシュ値を持つように設計します。具体的には、各文字を「出現順に0から始まる番号」に置き換えます。例えば "stt" であれば s→0、t→1 となり "011" に変換されます。同様に "abb" も "011"、"kmm" も "011" となるため一致と判定できます。一方、"xyz" は "012"、"aab" は "001" となるため除外されます。

この手法を使えば、辞書内のすべての単語を走査し、エンコード後のハッシュがパターンと一致するものだけを出力するだけで済みます。

サンプルコード

#include<iostream>
#include<unordered_map>
#include<unordered_set>
using namespace std;

// 文字列を数値列にエンコードする関数
string stringEncode(string str) {
    unordered_map<char, int> map;
    string encoded_str = "";
    int i = 0;
    for (char ch : str) {
        if (map.find(ch) == map.end())
            map[ch] = i++;
        encoded_str += to_string(map[ch]);
    }
    return encoded_str;
}

// パターンに一致する単語を辞書から検索する関数
void matchedPattern(unordered_set<string> dict, string pattern) {
    int patt_len = pattern.length();
    string hash = stringEncode(pattern);
    for (string word : dict) {
        if (word.length() == patt_len && stringEncode(word) == hash)
            cout << word << " ";
    }
}

int main() {
    unordered_set<string> dict = {"abb", "xyz", "aab", "kmm"};
    string pattern = "stt";
    matchedPattern(dict, pattern);
}

実行結果

kmm abb

コードの解説

stringEncode関数は、文字列内の各文字を初出順のインデックスにマッピングします。unordered_map を使って文字と番号の対応を管理し、まだ登録されていない文字には新しい番号を割り当てます。

matchedPattern関数では、まずパターンをエンコードしてハッシュを生成します。その後、辞書内の各単語について「長さがパターンと一致する」かつ「エンコード結果がパターンのハッシュと一致する」という2つの条件を満たす場合に出力します。長さのチェックを先に行うことで、不要なエンコード処理を省き、効率を高めています。

このアルゴリズムの計算量は、辞書内の単語数をN、単語の平均長をLとすると O(N×L) となり、非常に効率的です。