AcWing 142. 前缀统计
原题链接
简单
作者:
王小强
,
2021-02-08 14:14:45
,
所有人可见
,
阅读 337
Trie Tree
#include <iostream>
#include <vector>
#include <memory>
using namespace std;
class Trie {
public:
Trie() : root_(new TrieNode()) {}
void insert(const string& word) {
auto p = root_.get();
for (const auto& c : word) {
if (!p->children[c - 'a'])
p->children[c - 'a'] = new TrieNode();
p = p->children[c - 'a'];
}
++p->count;
}
int search(const string& word) {
int cnt = 0;
auto p = root_.get();
for (const auto& c : word) {
if (!p->children[c - 'a']) break;
p = p->children[c - 'a'];
cnt += p->count;
}
return cnt;
}
private:
struct TrieNode {
TrieNode() : count(0), children(26, nullptr) {}
~TrieNode() {
for (const auto& child : children) delete child;
}
int count; // 单词的个数
vector<TrieNode*> children;
};
unique_ptr<TrieNode> root_;
};
int n, m;
Trie trie;
int main(void) {
cin >> n >> m;
string word;
while (n--) {
cin >> word;
trie.insert(word);
}
while (m--) {
cin >> word;
cout << trie.search(word) << endl;
}
}