AcWing 835. Trie字符串统计
原题链接
简单
作者:
张立斌
,
2019-10-25 21:27:13
,
所有人可见
,
阅读 671
main函数
#include <iostream>
#include <string>
#include <strings.h>
#include <vector>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
Trie trie(1024);
for (int i = 0; i < n; ++i) {
string oper, str;
cin >> oper >> str;
if (oper == "I") {
trie.insert(str);
} else if (oper == "Q") {
cout << trie.count(str) << "\n";
}
}
return 0;
}
Trie树
class Trie {
class TrieNode {
public:
explicit TrieNode() : cnt(0) { bzero(children, sizeof(int) * CHILDREN_SIZE); }
static constexpr int CHILDREN_SIZE = 26;
inline int &operator[](unsigned char ch) { return children[ch - 'a']; }
inline int operator[](unsigned char ch) const { return children[ch - 'a']; }
int cnt;
private:
int children[CHILDREN_SIZE];
};
public:
explicit Trie(int capacity = 64) {
nodeVec.reserve(capacity);
nodeVec.emplace_back();
}
void insert(const string &str) {
int i = 0;
for (const unsigned char ch : str) {
int &child = nodeVec[i][ch];
if (!child) {
child = nodeSize();
nodeVec.emplace_back();
}
i = nodeVec[i][ch];
}
++nodeVec[i].cnt;
}
int count(const string &str) const {
int i = 0;
for (const unsigned char ch : str) {
i = nodeVec[i][ch];
if (!i) {
return 0;
}
}
return nodeVec[i].cnt;
}
private:
inline int nodeSize() const { return nodeVec.size(); }
vector<TrieNode> nodeVec;
};
constexpr int Trie::TrieNode::CHILDREN_SIZE;