最近學習了一下關于Trie的一些姿勢，感覺很實用。

終于不用每次看到字符串判重等操作就只想到hash了

關于Trie的定義，來自百度百科

在計算機科學中，Trie，又稱前綴樹或字典樹，是一種有序樹狀的數據結構，用于保存關聯數組，其中的鍵通常是字符串。

說的有點高級，我們不要管它，可以看這樣一張圖：

這棵Trie中的單詞共有:his,he,her,me,your

就是從根節點一直到某個有end（結尾）標記的點

可以發現，Tire其實就是把一些字符串的公用前綴字符存儲了下來

Tire的實現更是簡單：

建立一棵Trie，初始時只有一個空的根節點（編號為0）

每當插入或刪除時，如果當前字符在之前的操作中已經建立，然后直接利用即可，否則新建立一個節點并讓上一個節點連上它

當一個字符串結束時，給該節點做個記號，同時也可存儲些其它的信息

具體的實現方法也有兩種：鄰接表和鄰接矩陣

在Trie中，顯然用鄰接矩陣是很快的，但空間的開銷可能較大，如果題目說明范圍，那么空間允許的情況下可以使用

鄰接表還是一樣，比較省空間（畢竟要多少開多少）

這里用一道板子題來理解一下：

hihocoder 1366 : 逆序單詞

鄰接矩陣CODE

#include<iostream> #include<string> using namespace std; const int N=50005; struct node {bool end;int next[30]; }trie[N<<4]; string s; int n,ans,cnt; inline bool find(string s) {int now=0,len=s.size();for (register int i=0;i<len;++i){if (trie[now].next[s[i]-'a'+1]) now=trie[now].next[s[i]-'a'+1]; else return 0;if (i==len-1) return trie[now].end;} } inline void insert(string s) {int now=0,len=s.size();for (register int i=0;i<len;++i){if (trie[now].next[s[i]-'a'+1]) now=trie[now].next[s[i]-'a'+1]; else trie[now].next[s[i]-'a'+1]=++cnt,now=cnt;if (i==len-1) trie[now].end=1;} } int main() {register int i;for (cin>>n,i=1;i<=n;++i){cin>>s;string rs(s.rbegin(),s.rend());if (find(rs)) ++ans;insert(s);}cout<<ans;return 0; }

鄰接表CODE

#include<iostream> #include<cstring> #include<string> using namespace std; const int N=50005; struct node {bool end;char ch; }trie[N<<4]; struct edge {int to,next; }link[N<<4]; string s; int head[N<<4],n,ans,cnt; inline void add(int x,int y,char z) {link[y].to=y; trie[y].ch=z; link[y].next=head[x]; head[x]=y; } inline bool find(string s) {int now=0,len=s.size();for (register int i=0;i<len;++i){bool flag=0;for (register int j=head[now];j!=-1;j=link[j].next)if (trie[link[j].to].ch==s[i]) { flag=1; now=link[j].to; break; }if (!flag) return 0;if (i==len-1) return trie[now].end;} } inline void insert(string s) {int now=0,len=s.size();for (register int i=0;i<len;++i){bool flag=0;for (register int j=head[now];j!=-1;j=link[j].next)if (trie[link[j].to].ch==s[i]) { flag=1; now=link[j].to; break; }if (!flag) add(now,++cnt,s[i]),now=cnt;if (i==len-1) trie[now].end=1;} } int main() {register int i;memset(link,-1,sizeof(link));memset(head,-1,sizeof(head));for (cin>>n,i=1;i<=n;++i){cin>>s;string rs(s.rbegin(),s.rend());if (find(rs)) ++ans;insert(s);}cout<<ans;return 0; }

轉載于:https://www.cnblogs.com/cjjsb/p/8835042.html

總結

以上是生活随笔為你收集整理的关于Trie的一些算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。