In từ khớp mẫu CamelCase trong từ điển C++

Cho mảng chuỗi theo quy ước CamelCase (từ mới bắt đầu bằng chữ hoa) và một mẫu (chỉ chứa chữ hoa). In tất cả chuỗi khớp với mẫu. Ví dụ: từ điển {TutorialsPoint, ProgrammersPoint, ProgrammingLover, Tutorials}, mẫu "P". Kết quả: TutorialsPoint, ProgrammersPoint, ProgrammingLover.

Cây tiền tố chỉ dùng chữ hoa

Xây dựng Trie chỉ từ các ký tự in hoa của mỗi từ. Tìm mẫu trong Trie, sau đó in tất cả từ trong cây con đó.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

struct Node {
    Node* child[26] = {nullptr};
    bool isLeaf = false;
    vector words;
};

Node* newNode() { return new Node(); }

void insert(Node* root, const string& word) {
    Node* cur = root;
    for (char c : word) {
        if (islower(c)) continue;
        int idx = c - 'A';
        if (!cur->child[idx]) cur->child[idx] = newNode();
        cur = cur->child[idx];
    }
    cur->isLeaf = true;
    cur->words.push_back(word);
}

void printAll(Node* root) {
    if (root->isLeaf)
        for (auto& w : root->words) cout << w << endl;
    for (int i = 0; i < 26; i++)
        if (root->child[i]) printAll(root->child[i]);
}

bool search(Node* root, const string& pattern) {
    Node* cur = root;
    for (char c : pattern) {
        int idx = c - 'A';
        if (!cur->child[idx]) return false;
        cur = cur->child[idx];
    }
    printAll(cur);
    return true;
}

int main() {
    vector dict = {"Tutorial", "TP", "TutorialsPoint", "LearnersPoint", "TutorialsPointsPrograming", "programmingTutorial"};
    string pattern = "TP";
    Node* root = newNode();
    for (auto& w : dict) insert(root, w);
    if (!search(root, pattern)) cout << "Không tìm thấy";
    return 0;
}

Kết quả

TP
TutorialsPoint
TutorialsPointsPrograming