Trie | Billy2007&GoneTimeの世界

占坑。

填坑。

1. Trie是什么

Trie树又名字典树，是一种多叉树，常应用于关键词屏蔽等方面。

2. Trie树的构造

每个节点都有的：
- 一个自然数bih表示自己是几号节点 ~~，但通常可以忽略~~。
- 一个整数/字符id表示自己存的是什么，我习惯用整数存，并且用 $-1$ 表示啥都没存。
- 一个数组con，con[i]表示自己的子节点中有没有ASCII码是 $i$ 的节点，如果没有就是 $0$ ，有的话就是那个节点的bih。
- 一个bool值end表示是否有单词在这个节点结尾，如在 $\{114,114514\}$ 中，第一个 $4$ 的 $end$ 就是 $1$ 。
就根节点有的：
- 对于根节点，我们不存con除外的任何信息，只用一种方法表示这是根节点即可。
- 通常方法是直接把根节点的bih设成 $0$ 。
节点的初始化：
- 首先con肯定要全设成 $0$ ，因为现在还没有字符串，那么自然就不存在节点的链接，所以每一个点的con都全是 $0$ 。
- 然后end也要设成 $0$ ，原因同上。
- 接下来id要设成 $-1$ ，原因同上。

这些节点全部存在a数组里，数组的最大大小N=100001。

3. 节点的统计

Problem：给 $n$ 个字符串，做一棵Trie树，求Trie树的节点总数。

Solution：

对于每一个字符串 $k$ ，输入后循环遍历这个字符串。

当我们在字符串开头时，我们目前在的节点now=0，但是我们已经到第 $1$ 位了，已经有字符了，所以我们要看看有没有连接到字符串这一位的边。

如果有的话，那么就跳过去；

如果没有的话，那么就 ans++，并且新建一个节点，其中bih=ans，也就是当前不含根的节点总数；而id就是当前字符串的第 $1$ 位。

接下来，再从now节点连一条边到这个bih是ans的节点。

连边的代码就是a[now].con[k[i]]=ans;

接下来还要跳过去，也就是now=ans;

接下来到第二位。

当我们在字符串第 $2$ 位时，我们目前在的节点now=ans，但是我们已经到第 $2$ 位了，已经不是第 $1$ 位的字符了，所以我们要看看有没有连接到字符串这一位的边。

如果有的话，那么就跳过去；

如果没有的话，那么就 ans++，并且新建一个节点，其中bih=ans，也就是当前不含根的节点总数；而id就是当前字符串的第 $2$ 位。

接下来，再从now节点连一条边到这个bih是ans的节点。

连边的代码就是a[now].con[k[i]]=ans;

接下来还要跳过去，也就是now=ans;

然后就这样跳下去，直到最后一位……

当我们在字符串第 $|k|$ 位时，我们目前在的节点now=ans，但是我们已经到第 $|k|$ 位了，已经不是第 $|k|-1$ 位的字符了，所以我们要看看有没有连接到字符串这一位的边。

如果有的话，那么就跳过去；

如果没有的话，那么就 ans++，并且新建一个节点，其中bih=ans，也就是当前不含根的节点总数；而id就是当前字符串的第 $|k|$ 位。

接下来，再从now节点连一条边到这个bih是ans的节点。

连边的代码就是a[now].con[k[i]]=ans;

接下来还要跳过去，也就是now=ans;

好了，跳到了。

但是，这意味着，这个字符串已经走到了行程的终点。

既然到了终点，那么就得做个标记，也就是a[now].end=1，表示从根节点到now，是一个信息。~~比如在七号节点上边做一个end标记就可能意味着 $1919810$ 是个很臭的数字（bushi~~

done.

一个一个字符串读入完， ans+1（包括根节点也要算进去） 就是最终的答案。

附：洛谷P2580代码

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=10001,inf=0x3f3f3f3f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}
struct point{
	int end;
	int id,con[27];
	point(){
		id=-1;
		ms(con,0);
		end=0;
	}
}a[N*51];
char z[N][51],k[51],q[51];
int m,w,ans=1,pp;
void dfs(int now){
	fs(i,60,127,1) if(a[now].con[i]){
		printf("%d->(%c",now,i);
		printf(" %d)\n",a[now].con[i]);
		system("pause");
		dfs(a[now].con[i]);
	}
	printf("886 from %d\n",now);
	if(a[now].end) printf("%d is end!\n",now);
}
int main(){
	pp=read();
	while(cin>>z[++w]){
		if(w>=pp) break;
	}
	fs(lzl,1,w,1){
		strcpy(k,z[lzl]);
		int now=1,l=strlen(k)-1;
		for(ll i=0;k[i];i++){
			if(a[now].con[k[i]-'a']){
				now=a[now].con[k[i]-'a'];
				if(i==l) a[now].end=1;
			}else{
				ans++;
				a[ans].id=k[i]-'a';
				a[now].con[k[i]-'a']=ans;
				now=ans;
				if(i==l) a[now].end=1;
			}
		}
	}
	m=read();
	ans=1;
	
	fs(lzl,1,m,1){
		cin>>k;bool f=0;
		int now=1,l=strlen(k)-1;
		for(ll i=0;k[i];i++){
			//printf("%d\n",now);
			if(a[now].con[k[i]-'a']){
				now=a[now].con[k[i]-'a'];
				//printf("%d\nqwq\n",now);
			}else{
				puts("WRONG");
				f=1;
				break;
			} 
		}
		if(a[now].end==1&&!f){
			a[now].end=2;
			puts("OK");
		}else if(a[now].end==0&&!f){
			puts("WRONG");
		}else if(!f){
			puts("REPEAT");
		}
	}
	return 0;
}