AcWing 835. Trie字符串统计
原题链接
简单
作者:
233
,
2019-10-04 17:44:51
,
所有人可见
,
阅读 694
C++ 代码
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
class Trie
{
public:
Trie() { memset(links, NULL, sizeof links); };
~Trie() {};
Trie* links[26];
bool isEnd;
int cnt = 0;
void Insert_string(string str) {
auto head = this;
for (auto ch : str) {
int tmp = ch - 'a';
if (head->links[tmp] == nullptr)
head->links[tmp] = new Trie();
head = head->links[tmp];
}
head->isEnd = true, ++head->cnt;
}
int Search_string(string str) {
auto head = this;
for (auto ch : str) {
if (head->links[ch - 'a'])
head = head->links[ch - 'a'];
}
if (head == NULL || head->isEnd == false)return 0;
return head->cnt;
}
};
int main(void) {
Trie A;
int n; cin >> n;
while (n--) {
char ch; string str;
cin >> ch >> str;
if (ch == 'I')A.Insert_string(str);
else cout << A.Search_string(str) << endl;
}
return 0;
}