以 app 开头的有几个

词库是 apple、app、apply、banana。运行下面这段程序：

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#include <algorithm>
#include <map>

struct TNode {
    map<char, TNode*> kids;
    bool end = false;      // 有没有一个词在这里结束
};

TNode* build_trie(const vector<string>& words) {
    TNode* root = new TNode();
    for (const string& w : words) {
        TNode* node = root;
        for (char ch : w) {
            if (!node->kids.count(ch)) node->kids[ch] = new TNode();
            node = node->kids[ch];
        }
        node->end = true;
    }
    return root;
}

TNode* walk(TNode* t, const string& pre) {
    // 沿着前缀往下走，走不通返回 nullptr
    TNode* node = t;
    for (char ch : pre) {
        if (!node->kids.count(ch)) return nullptr;
        node = node->kids[ch];
    }
    return node;
}

void collect(TNode* node, const string& cur, vector<string>& out) {
    // 把 node 下面所有的词收进 out
    if (node->end) out.push_back(cur);
    for (auto& kv : node->kids) collect(kv.second, cur + kv.first, out);
}

int count_prefix(TNode* t, const string& pre) {
    TNode* node = walk(t, pre);
    if (node == nullptr) return 0;
    vector<string> out;
    collect(node, pre, out);
    return (int)out.size();
}

int main() {
    TNode* t = build_trie({"apple", "app", "apply", "banana"});
    cout << count_prefix(t, "app") << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）