很早以前就搞了当时没写, 因为当时从来不写…😭
Tire树(字典树)
从根节点开始将字符串的每一个字符对应一个点, 形成一个路径
tire树擅长求的东西:
1. 一个字符串的前缀有多少个
2. 一个字符串是多少个字符串的前缀
void insert(string &s) // 插入字符串s到tire
{
int p = 0;
for (auto i : s)
{
int k = i - 'a'; // 表示p要指向的字符
if (!son[p][k]) son[p][k] = ++idx; // 字符p再k的子节点中不存在, 建立一个新的节点
p = son[p][k];
}
st[p]++; // 以节点u结尾
}
int query(string &s)
{
int p = 0;
for (auto i : s)
{
int k = i - 'a';
if (!son[p][k]) return 0; // 同理
p = son[p][k];
}
return st[p];
}