今天上午省选字符串......只会KMP、连hash都不会的我被大佬虐惨了......于是我要发奋图强学习字符串，学习字符串当然就要从Trie树这种可爱的数据结构开始啦！！！
一、什么是Trie树？？？
字典树，顾名思义，用来保存一些字符串。
二、Trie树的优势/用途？？？
那么就有人会问了：保存一些字符串，为什么不直接用数组？？？答案是显然的，你会收获MLE的好结果，于是我们考虑节省空间来保存他们的数据结构，于是Trie树就应运而生了！！！
三、核心思想？？？保存方法？？？
考虑存储两个单词ABA和ABC，我们可以利用他们有着共同前缀“AB”（因此Trie又被称为“前缀树”），于是我们可以建立一棵形如这样的Trie树：
A
|
B
|
————
| |
A C
我们发现，我们用了四个字符的空间，就存了六个字符，再加上动态开点，使得Trie的空间复杂度十分优秀。
四、Trie常用操作
插入/查询 是Trie的最基本操作：
插入代码如下（有详细注释，查询与之相似）
1 void insert(char *s) 2 { 3 int u=0,len=strlen(s+1); 4 //len为字符串长，u指向当前节点，最开始是根节点，指向0 5 for(int i=1;i<=len;i++) 6 { 7 int c=idx(s[i]);//查询s[i]对应的数字 8 if(!ch[u][c])ch[u][c]=++cnt;//如果没有这个点，开一个新节点 9 u=ch[u][c];//顺着走一位 10 } 11 } Trie插入五、例题：
洛谷P2580
解析：
Trie树裸题，将所有学生的名字放进Trie树中。对于询问，如果一个人的名字中有的点为空，那么就是错的，如果是第一次查询，那么就是对的，否则就是重复了。
参考代码如下：
1 // luogu-judger-enable-o2 2 #include<iostream> 3 #include<cstring> 4 #include<cstdio> 5 #define N 500050 6 using namespace std; 7 struct Trie 8 { 9 int val[N],ch[N][26],cnt; 10 int idx(char c){return c-'a';} 11 void insert(char *s) 12 { 13 int u=0,len=strlen(s+1); 14 for(int i=1;i<=len;i++) 15 { 16 int c=idx(s[i]); 17 if(!ch[u][c])ch[u][c]=++cnt; 18 u=ch[u][c]; 19 } 20 } 21 int search(char *s) 22 { 23 int u=0,len=strlen(s+1); 24 for(int i=1;i<=len;i++) 25 { 26 int c=idx(s[i]); 27 if(!ch[u][c])return 0; 28 u=ch[u][c]; 29 } 30 if(!val[u]){val[u]=1;return 1;} 31 return 2; 32 } 33 }trie; 34 int n,m; 35 char s[25000]; 36 int main() 37 { 38 ios::sync_with_stdio(0); 39 cin>>n; 40 for(int i=1;i<=n;i++) 41 { 42 cin>>(s+1); 43 trie.insert(s); 44 } 45 cin>>m; 46 for(int i=1;i<=m;i++) 47 { 48 cin>>(s+1); 49 int res=trie.search(s); 50 if(res==0)cout<<"WRONG"<<endl; 51 else if(res==1)cout<<"OK"<<endl; 52 else cout<<"REPEAT"<<endl; 53 } 54 return 0; 55 } 洛谷P2580
转载于:https://www.cnblogs.com/szmssf/p/11489090.html
相关资源：JAVA上百实例源码以及开源项目