「Day-2 提高笔记-字典树」

字典树

字典树是什么？

理论知识

1. 插入操作

我们在插入的时候，先从根节点去向下遍历。对于字符串 \(S\) 的一位 \(S_i\)。

• 如果发现其在字典树中当前节点下有这个字符 \(S_i\)，则继续向下，在向下的过程中每次给当前节点的次数加 \(1\)，记录字符串前缀数量。
• 若无这个字符，则开辟一个新的节点，记录节点编号，继续向下。

2. 查询前缀数量

我们在查询前缀的时候，先从根节点去向下遍历。对于字符串 \(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;
}