[Tire
]
【杂言】：
本来因为(KMP)没有打完，所以还没有打算进行(Tire)字典树的学习，既然(gyh)学长讲了，那就自然整理一下了。也正是因为今天，我开放了所有的学习笔记。
【前置芝士】：
基础图论 ， 只需要明白建树即可。无需其他的太多的东西，反正我是这么认为的。，有效状态自动机
【算法流程】：
(Tire)字典树可以用来解决"一个字符串是否出现过"，并以这个问题来简要的概述一下流程。
输入(3)个字符串， ("Zmon" , "Zmck" "les") , 这(3)个 ， 查询一下"Zmon"和"Zmaa"是否存在。
我们首先建一颗树 ， 节点是一个虚点(now)，然后加入：
- 加入(Zmon), 就是(now o Z o m o o o n) 建一条树边
- 加入(Zmck),发现在建立(Z,m)时，早就有已经建立过的树边了，那么这时候，我们也只需要在(m)的后面建树边也就是(m o c o k) ,
- 加入(llon) ,发现(l)节点没有建立，那么我们建一个(l)这个节点，连接虚点，从而形成一条树边，也就是$now o l o e o s $ 这一条树边 。 描述的很清楚了，建完之后就是下面这一幅图，比较难看，将就一下。
下面就是(Zmon)的查询了，我们可以看到，查询是字符进行比较， 比较第一个字符是有的，也就是(Z) , 我们发现有两条树边由(Z)作为起始点，并且下一个节点是(m)， 那么我们匹配的时候，继续从(m)进行匹配，看一下(m)连接的节点，有一个(o)，那么,沿着树边继续寻找，找到了(n)并且下面没有节点，那么匹配（其实意思也就是从now的下一个节点一直到叶子节点就是一个单词）
关于(Zmaa) 的查询,我们运用上帝视角发现，其实没有，我们还是模拟一下计算机吧，一直到(m)就不再赘述了，和上段一致 ， 同时 ，到了(a)这个字符匹配，发现这个节点中是没有这个的，那么我们就直接(return false),就(OK)了，证明这一个点不存在
[【例题】] (https://www.luogu.com.cn/problem/P2580)：
题目就不赘述了，直接上代码，如是不会，详解其题解。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#define int long long
const int kmaxn = 2e6 ;
const int kbase = 13331 ;
const int kmod = 1e7 + 1;
using namespace std ;
inline int read()
{
int x = 0 , f = 1 ; char ch = getchar() ;
while(!isdigit(ch)) { if(ch == '-') f = - 1 ; ch = getchar() ; }
while( isdigit(ch)) { x = x * 10 + ch - '0' ; ch = getchar() ; }
return x * f ;
}
struct Tire
{
int ch[kmaxn][27] , now ,val[kmaxn] ;
//ch是第几个单词出现的次数
Tire()
{
now = 1 ; //建立虚点
memset(ch[0] , 0 , sizeof(ch[0])) ;
memset(val , 0 , sizeof(val)) ;
}
void insert(char *s) //插入一个单词
{
int p = 0 ;
int lth = strlen(s+1) ;
for(int i = 1 ; i <= lth ; i++)
{
if(!ch[p][s[i] - 'a']) //如果这一个节点不存在，那就新建节点
{
memset(ch[now] , 0 , sizeof(ch[now])) ;
ch[p][s[i] - 'a'] = now++ ;
}
p = ch[p][s[i]-'a'] ;//继续向下寻找
}
}
int query(char *s)
{
int p = 0 , lth = strlen(s+1) ;
for(int i = 1 ; i <= lth ; i++)
{
if(!ch[p][s[i] - 'a']) return 0 ;
p = ch[p][s[i]-'a'] ;
}
if(!val[p])
{
val[p] = 1 ; return 1 ;
}
return 2 ;
}
}tire;
char s[kmaxn] ;
int m , n ;
signed main()
{
n = read() ;
for(int i = 1 ; i<= n ;i++)
{
scanf("%s" ,s+1) ;
tire.insert(s) ;
}
m = read() ;
while(m--)
{
scanf("%s" , s+1) ;
int opt = tire.query(s) ;
if(opt == 0) printf("WRONG
") ;
if(opt == 1) printf("OK
") ;
if(opt == 2) printf("REPEAT
") ;
}
return 0 ;
}