字典树
字典树是什么？
理论知识
- 插入操作
我们在插入的时候，先从根节点去向下遍历。对于字符串 \(S\) 的一位 \(S_i\)。
- 如果发现其在字典树中当前节点下有这个字符 \(S_i\)，则继续向下，在向下的过程中每次给当前节点的次数加 \(1\)，记录字符串前缀数量。
- 若无这个字符，则开辟一个新的节点，记录节点编号，继续向下。
- 查询前缀数量
我们在查询前缀的时候，先从根节点去向下遍历。对于字符串 \(S\) 的一位 \(S_i\)。
- 若在字典树当前节点下没有 \(S_i\)，则证明没有以该前缀为开头的单词。
- 否则就继续向下，直到 \(S_n\)，最后返回该节点数下的前缀数量。
时间复杂度
对于一个长度为 \(n\) 字符串。
\(Insert\) 和 \(query\) 的时间复杂度都是 \(O(n)\)。
代码实现
P8306 【模板】字典树
#include<bits/stdc++.h>
using namespace std;const int MAXN = 3e6 + 5;
int T;
int n,q;
char s[MAXN];
int ch[MAXN][100],cnt[MAXN],id = 0;int got(char c){if(c >= 'A' && c <= 'Z') return c - 'A';if(c >= 'a' && c <= 'z') return c - 'a' + 26;return c - '0' + 52;
}void Insert(char *s){int now = 0;for(int i = 0;s[i];i ++){int v = got(s[i]);if(!ch[now][v]){ch[now][v] = ++ id;}now = ch[now][v];cnt[now] ++; }return;
}int query(char *s){int now = 0;for(int i = 0;s[i];i ++){int v = got(s[i]);if(!ch[now][v]) return 0;now = ch[now][v];}return cnt[now];
}void Clear(){memset(ch, 0, sizeof(ch[0]) * (id + 1));memset(cnt, 0, sizeof(cnt[0]) * (id + 1));id = 0;
}signed main(){scanf("%d",&T);while(T --){scanf("%d%d",&n,&q);for(int i = 1;i <= n;i ++){scanf("%s",s);Insert(s);}for(int i = 1;i <= q;i ++){scanf("%s",s);cout << query(s) << '\n';}Clear();}return 0;
}
