「学习笔记」字典树

「学习笔记」字典树

Trie Tree

1.作用

通过字典树可以快速、简单地查找字符串；节省存储空间。

2.实现

例如：
现有 ab , ac , d 3个字符串

那么塞进Trie树里面就是这样的：

顺着以前已经确立的字母往下走，
在字符串的终点打上标记即可。

图中的字母可以理解为树的边权，
经过的路线所对印的字符串就是把这些权值按顺序拼凑起来了

字典树的操作有简单的两种为 插入 & 查询

插入操作

简单总结一下的话呢，
就是该字符如果没有在对应的根下面出现过那么就插入，否则就顺着树往下走

void insert() {int root = 0, len = strlen(str);for (int i=0; i<len; i++) {char id = str[i];if (tree[root][id] == 0) {tree[root][id] = ++tot;}root = tree[root][id];}flag[root]++;
}

链式前向星实现

void add(int u , int data) {tree[++cnt].id=data;tree[cnt].next=head[u];head[u]=cnt;
}void insert() {int root = 1, len = strlen(str);for (int i=0; i<len; i++) {int id = str[i];bool flag = false;for (int i=head[root]; i; i=tree[i].next) {if (tree[i].id == id) {flag = true;root = i;break;}}if (!flag) {add(root, id);root = cnt;}}flag[root]++;
}

查询操作

标记已经打好了
判断有没有打标记总会吧
不会我也没办法

3.例题

题目描述

新学期开学有几天了，Capo发现班上有一个老师，这位老师喜欢每天上课前先点名，并且是随机抽点。今天，Capo突然发现自己被点到了两次，于是Capo开始质疑老师的点名是否有重复或误报为其他班的同学。当然Capo可不想一个个比较，所以他把这个任务交给了你，当然Capo会提供班上人数n和他们的名字，同时Capo也会记下老师报的名字。

样例输入

5
a
b
c
ad
acd
3
a
a
e

样例输出

OK
REPEAT
WRONG

AC代码：

#include <bits/stdc++.h>
using namespace std;int tree[500005]['z'], flag[500005], tot;
char str[55];void insert() {int len = strlen(str), root = 0;for (int i=0; i<len; i++) {char id = str[i];if (tree[root][id] == 0) {tot++;tree[root][id] = tot;}root = tree[root][id];}flag[root]++;
}int search() {int len = strlen(str), root = 0;for (int i=0; i<len; i++) {char id = str[i];if (tree[root][id] == 0) {return 0;}root = tree[root][id];}if (flag[root] == 0) {return 0;}flag[root]++;return flag[root];
}int main() {int n, m;scanf("%d",&n);for (int i=1; i<=n; i++) {scanf("%s",&str);insert();}scanf("%d",&m);for (int i=1; i<=m; i++) {scanf("%s",str);int temp = search();if (temp == 0) {printf("WRONGn");}if (temp == 2) {printf("OKn");}if (temp > 2)  {printf("REPEATn");}}return 0;
}