【指针法】:内存池优化
关于内存池的解释:AcWing 826. 单链表 【指针法】:内存池优化
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct trieNode {
char val; // val是结点的数据域(值value)
trieNode* son[26]; // son是结点的子树数组
};
/*
cnt[]既是标记数组也是计数数组,cnt[i]大于0表示当前结点是一个单词的末尾,cnt[i]的值记录该单词出现的次数
nodeArray是内存池,预先申请了略大于1e5的内存空间
trie是trie树的根结点,idx指向是当前内存池中可用的结点
*/
int cnt[N];
trieNode* nodeArray = new trieNode[N];
trieNode* trie = nodeArray, *idx = nodeArray + 1;
void insert(char* str) {
trieNode* ptr = trie;
for (int i = 0; str[i]; ++ i) {
int j = str[i] - 'a';
if (ptr->son[j] == NULL) { // 如果该字符还没有被记录
trieNode* Node = idx ++; // 从内存池中取出一块内存空间(等价于new一个新结点)
Node->val = str[i]; // 记录该字符的值
ptr->son[j] = Node; // 将该字符插入trie树
}
ptr = ptr->son[j];
}
cnt[ptr - trie] ++; // 记录当前单词出现的次数
}
int query(char* str) {
trieNode* ptr = trie;
for (int i = 0; str[i]; ++ i) {
int j = str[i] - 'a';
if (ptr->son[j] == NULL) return 0;
ptr = ptr->son[j];
}
return cnt[ptr - trie];
}
signed main() {
int n;
char str[N], oper;
scanf("%d\n", &n);
while (n --) {
scanf("%c %s\n", &oper, str);
if (oper == 'I') insert(str);
else printf("%d\n", query(str));
}
trie = idx = NULL, delete []nodeArray;
return 0;
}