字典树（单词查找树、Trie树）
题目
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int f[N][26], idx, cnt[N];
void insert(char str[])
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if(!f[p][u]) f[p][u] = ++idx;
p = f[p][u];
}
cnt[p]++;
}
int query(char str[])
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if(!f[p][u]) return 0;
p = f[p][u];
}
return cnt[p];
}
int main()
{
int n;
cin >> n;
char str[N];
for(int i = 1; i <= n; i++)
{
char op;
cin >> op >> str;
if(op == 'I') insert(str);
else cout << query(str) << '\n';
}
}关于存储大小
一般是 元素数*分支数
也可以 元素数
原文地址：https://blog.csdn.net/m0_73669127/article/details/142766165
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！