ACM入门之【字典树/Trie】
入门 字典 ACM Trie
2023-09-11 14:15:52 时间
字典树，英文名 trie。顾名思义，就是一个像字典一样的树。
常用模板：
const int N=1e5+10; //注意: N的大小是所有的字符串的总长度,因为最坏的情况下是一个字符就是一个结点
int son[N][26],cnt[N],idx;
void insert(string s)//插入
{
int p=0;
for(int i=0;i<s.size();i++)
{
int u=s[i]-'a';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
cnt[p]++;
}
int query(string s)//查找
{
int p=0;
for(int i=0;i<s.size();i++)
{
int u=s[i]-'a';
if(!son[p][u]) return 0;
p=son[p][u];
}
return cnt[p];
}