字典樹，高端點就是tire樹，或者前綴樹，其實就是一個挺簡單的算法，但一直沒學，昨晚上訓練有涉及到，今天來突擊一下，發現不是那么難

先插眼一個大牛的博客（因為實在懶得復制粘貼了）：

https://blog.csdn.net/weixin_39778570/article/details/81990417

然后就是我模仿原理自己寫的string類的模板：

const int N=2e3+100;//節點數int k;//節點編號int trie[N][26];//儲存每一條邊 trie[節點數][字符數]bool color[N];//判斷某一個字符串是否出現過int newnode()//動態初始化 {k++;for(int i=0;i<26;i++)trie[k][i]=0;pre[k]=0;return k; }void insert(string& s)//插入 {int pos=0;for(int i=0;i<s.size();i++){int to=s[i]-'a';if(!trie[pos][to])trie[pos][to]=newnode();pos=trie[pos][to];}color[pos]=true; }bool search(string& s)//查找 {int pos=0;for(int i=0;i<s.size();i++){int to=s[i]-'a';if(!trie[pos][to])return false;pos=trie[pos][to];} return color[pos]; }void init()//初始化 {k=-1;newnode(); }

?

總結

以上是生活随笔為你收集整理的(转)字典树原理+实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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