C++でキャメルケース表記の辞書からパターンに一致するすべての単語を出力する方法

この問題では、キャメルケース（CamelCase）で記述された文字列の配列とパターンが与えられ、そのパターンに一致する配列内のすべての文字列を出力することが求められます。

用語の説明

文字列の配列とは、要素がすべて文字列型である配列のことです。

キャメルケース（camelCase）は、プログラミングで広く使われている命名規則の一つです。複合語を表記する際に、2語目以降の先頭文字を大文字にし、残りの文字を小文字で記述します。

例：iLoveProgramming

問題の定義

課題：指定されたパターンに一致するすべての文字列を見つけ出すことです。

入出力例

入力： "TutorialsPoint", "ProgrammersPoint", "ProgrammingLover", "Tutorials"
パターン： 'P'
出力： "TutorialsPoint", "ProgrammersPoint", "ProgrammingLover"

解説：この例では、大文字の'P'を含むすべての文字列が対象となっています。

解決アプローチ：トライ（Trie）構造の活用

この問題を効率的に解くには、トライと呼ばれる木構造のデータ構造を活用します。具体的な手順は以下の通りです。

1. 辞書内の各単語について、大文字のみをキーとしてトライに挿入します（小文字はスキップします）。
2. 各トライのノードには、そのノードに至る単語のリストを保持します。
3. パターンを使ってトライを検索し、一致するノードから到達可能なすべての単語を出力します。

この方法では大文字だけを比較対象とするため、キャメルケースの各単語の先頭文字だけでパターンマッチングが可能になります。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
struct TreeNode{
    TreeNode* children[26];
    bool isLeaf;
    list<string> word;
};
TreeNode* getNewTreeNode(void){
    TreeNode* pNode = new TreeNode;
    if (pNode){
        pNode->isLeaf = false;
        for (int i = 0; i < 26; i++)
            pNode->children[i] = NULL;
    }
    return pNode;
}
void insert(TreeNode* root, string word){
    int index;
    TreeNode* pCrawl = root;
    for (int level = 0; level < word.length(); level++){
        if (islower(word[level]))
            continue;
        index = int(word[level]) - 'A';
        if (!pCrawl->children[index])
        pCrawl->children[index] = getNewTreeNode();
        pCrawl = pCrawl->children[index];
    }
    pCrawl->isLeaf = true;
    (pCrawl->word).push_back(word);
}
void printAllWords(TreeNode* root){
    if (root->isLeaf){
        for(string str : root->word)
            cout << str << endl;
    }
    for (int i = 0; i < 26; i++){
        TreeNode* child = root->children[i];
        if (child)
            printAllWords(child);
    }
}
bool search(TreeNode* root, string pattern){
    int index;
    TreeNode* pCrawl = root;
    for (int level = 0; level <pattern.length(); level++) {
        index = int(pattern[level]) - 'A';
        if (!pCrawl->children[index])
            return false;
        pCrawl = pCrawl->children[index];
    }
    printAllWords(pCrawl);
    return true;
}
void findAllMatch(vector<string> dictionary, string pattern){
    TreeNode* root = getNewTreeNode();
    for (string word : dictionary)
        insert(root, word);
    if (!search(root, pattern))
        cout << "No match found";
}
int main(){
    vector<string> dictionary = { "Tutorial" , "TP" , "TutorialsPoint" , "LearnersPoint", "TutorialsPointsPrograming" , "programmingTutorial"};
    string pattern = "TP";
    findAllMatch(dictionary, pattern);
    return 0;
}

出力結果

TP
TutorialsPoint
TutorialsPointsPrograming

コードの解説

このプログラムの動作を簡単に説明します。

• TreeNode構造体：アルファベットの大文字A〜Zに対応する26個の子ポインタ、葉ノードかどうかを示すフラグ、および単語のリストを保持します。
• insert関数：単語をトライに挿入します。小文字は無視し、大文字のみをノードのキーとして使用します。
• search関数：パターンに従ってトライを辿り、一致するノードを見つけます。存在しない場合はfalseを返します。
• printAllWords関数：指定されたノード以下に存在するすべての単語を再帰的に出力します。

このアルゴリズムの構築にかかる時間計算量は、辞書内の全単語に含まれる大文字の数の合計に比例します。また、パターン検索はパターン長に比例した時間で完了するため、大量の単語を扱う場合にも効率的に動作します。