AcWing 835. Trie字符串统计 C++
原题链接
简单
作者:
LaChimere
,
2021-05-19 14:08:58
,
所有人可见
,
阅读 152
C++
#include <iostream>
using namespace std;
const int MAXSIZE = 100010;
int trie[MAXSIZE][26], cnt[MAXSIZE], idx;
string str;
void insert(const string& str) {
int p = 0;
for (char c : str) {
int ch = c - 'a';
if (!trie[p][ch]) {
trie[p][ch] = ++idx;
}
p = trie[p][ch];
}
cnt[p]++;
}
int query(const string& str) {
int p = 0;
for (char c : str) {
int ch = c - 'a';
if (!trie[p][ch]) {
return 0;
}
p = trie[p][ch];
}
return cnt[p];
}
int main() {
int n;
cin >> n;
while (n--) {
char op;
cin >> op >> str;
if (op == 'I') {
insert(str);
} else {
cout << query(str) << endl;
}
}
return 0;
}