Trie字典樹
目錄
Trie字典樹
例題
1.什麼是字典樹？
2.字典樹的作用及性質
3.建樹
Code：
效果圖：
4.查詢
Code：
5.優勢
6.回到例題
Code：
7.結束語
8.練習：
例題
給出n個字元串，以及m個詢問。每次詢問讀入一個字元串，求該字元串是多少個字元串的字首
每個字元串長度小于10^2，n和m小于10^5。
【樣例輸入】
4
anan
amn
aman
anann
3
ana
ama
a
【樣例輸出】
2
1
4
樸素算法：暴力搜尋，對于每個詢問，把所有的n個字元串搜尋一遍，統計答案。時間複雜度大于10^10。顯然，這樣時間是非常大的。
如果要優化時間的話，我們就可以使用字典樹。
1.什麼是字典樹？
字典樹，又叫做Trie樹，顧名思義，首先它必須得是一棵樹。
**而且它是用來儲存字元串的！！！** 就像一本字典一樣，裡面什麼都有(隻要你存了)
它的根節點為空，其餘每個節點代表一個字元。從根節點開始，沿着一定的路徑，加上沿途遇到的字元，到達每個節點，都能得到對應的一個字元串。
2.字典樹的作用及性質
字典樹的作用
1、可以判斷一個字元串之前是否出現過。
2、可以判斷目前這個字元串是多少個字元串的字首。
3、等等等等......
其實大概就這些了，具體應用就要靠讀者自己去思考了。
字典樹的性質
1、沿着字典樹一直走，如果經過一個被标記的點，那麼從根節點到目前這個節點所經過的所有字元組成的字元串一定出現過，也就是說如果一個沒有出現過的字元串在字典樹上是走不出來的。
2、不論沿着字典樹怎麼走，都不會走到兩個被标記的不同的點，使得它們沿途經過的點是完全相同的，意思就是說相同的字元串在字典樹裡面隻會出現一次。
3.建樹
設trie[i].to[c]表示字典樹中編号i節點的兒子中，字元c的兒子的編号。
設trie[i].bz表示目前這個節點是否是一個字元串的結尾(1是0不是)。
設tot表示目前Trie樹裡節點的總數(也可以看做編号)，當我們要加入一個點的時候就将編号+1。
一開始字典樹是一棵空樹，不，實際上不是，因為它有一個為空的根節點。
為了節約空間，隻有需要用到的節點，才會被開啟，其餘都是不存在的。（這句話如果不好了解可以看看操作步驟和代碼）
設目前我們将字元串s加入字典樹，步驟如下：
1、先将目前的節點賦成根節點，之後我們從左到右掃s這個字元串(注意字典樹的根節點為空)；
2、如果目前的點後面沒有一個s[i]的字元，那就在目前這個點的下面加上s[i]這個字元的點；
3、然後沿着字典樹往s[i]這個字元走下去。
4、當字元串中所有的字元都加入完了這棵字典樹時，要将這個字元串的最後一個字元的編号打上标記，表示目前這個節點是一個字元串的結尾。
Code：
int tot=0;//tot一定要是根節點的編号，因為當根節點往下走的時候tot+1不能和根節點的編号一樣
void insert(char s[])
{
int t=0;//根節點的編号為0
for (int i=1;i<=len;i++)//循環枚舉s的每一位
{
int k=s[i]-'a'+1;//将字母轉換成數字
if (trie[t].to[k]==0) trie[t].to[k]=++tot;
//如果目前的節點下面沒有k這個數字(字元）就在目前節點下加入k這個點，同時将它編号為tot；
//如果目前節點已經有了k這個數字(字元)就不用再加
t=trie[t].to[k];//之後再沿着字典樹走下去
}
trie[t].bz=true;//表示目前節點是一個字元串的結尾
}
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]);
len=strlen(s[i]);
insert(s[i]);
}
效果圖：
如前面的樣例，四個字元串用字典樹儲存的效果。
anan
amn
aman
anann
同時，圖中被紅線畫出來的點都被打了标記；根節點的編号為0，從根節點往下的第一個a的編号是1，以此類推，編号為1的a下面的n編号為2，編号為2的n下面的a編号為3，編号為3的a下面的n編号為4。編号為1的a下面的m編号為5，編号為5的m下面的n編号為6。編号為5的m下面的a編号為7，編号為7的a下面的n編号為8。最後編号為4的n下面的n編号為9。
4.查詢
如果我們要查詢一個字元串是否在字典樹中出現該怎麼辦呢？
1、首先，我們按照這個字元串中的每個字元在字典樹中走下去。
2、如果有一個字元沒有出現在字典樹中，那麼這個字元串就沒有出現，直接退出。
3、如果掃完了這個字元串，也走完了這棵字典樹，那麼我們就判斷一下目前這個節點是否有标記，有标記就說明這個字元串出現過。
Code：
int tot=0;//根節點編号為0
int find()
{
scanf("%s",s+1);//判斷s是否出現過
int len=strlen(s+1);//s的長度為len
int t=0;//目前節點為根節點
for (int i=1;i<=len;i++)
{
int k=s[i]-'a'+1;//将字元轉換為數字
t=tree[t].to[k];//沿着字典樹走下去
if (t==0) break;//如果字典樹中沒有這個節點就說明這個字元串沒有出現，退出
}
return tree[t].bz;//如果目前編号t是一個字元串的結尾，就說明這個字元串出現過，否則就沒有出現。
}
5.優勢
由上圖顯而易見，當多個字元串有相同字首時，相同的字元隻會儲存一次，節省了很大的空間。
同時，用字典樹儲存字元串，可以對許多關于字元串字首的題目有很大幫助。
6.回到例題
顯然，這題我們需要先用n個字元串建立一棵字典樹。
與此同時，記錄tree[t].bz表示n個字元串中字首為string[t]的個數，string[t]為字典樹中到節點i處所表示的字元串（此處隻是為了友善說明，在實作時這個string數組并不存在）。每到一個節點t，就給tree[t].bz+1。
如何處理詢問？
将詢問串放入字典樹中，類似建樹的方式往下走。如果對應的節點不存在，則直接傳回并輸出0。
否則一直走到該串的末尾，對應的tree[i].bz即為答案。
Code：
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,m,len,tot=0;
struct tree{
int to[27],bz;
}trie[100000];
char s[1000][1000];
void insert(char s[])
{
int t=0;
for (int i=1;i<=len;i++)
{
int k=s[i]-'a'+1;
if (trie[t].to[k]==0) trie[t].to[k]=++tot;
t=trie[t].to[k];
trie[t].bz++;
}
}
int find(char s[])
{
int t=0;
for(int i=1;i<=len;i++)
{
int k=s[i]-'a'+1;
t=trie[t].to[k];
if(t==0) break;
}
return trie[t].bz;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
len=strlen(s[i]+1);
insert(s[i]);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",s[i]+1);
len=strlen(s[i]+1);
printf("%d\n",find(s[i]));
}
return 0;
}
7.結束語
此時，相信你已經學會了。字典樹模闆都是一樣的，對于不同的題目不同的要求，都以模闆為基礎，再按需添加各種操作，難題便迎刃而解。
面對更多的困難與挑戰，需要你更多思考、靈活變通，一切都不是問題！
8.練習：
1.1099. 尋找字元串
2.5795. 【2018提高組】模拟A組&省選 詞典
作者：zsjzliziyang
QQ:1634151125
轉載及修改請注明
本文位址:https://blog.csdn.net/zsjzliziyang/article/details/81869305
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)