Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。

trie樹的應用：

1.有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節，內存限制大小是1M。返回頻數最高的100個詞。

2.1000萬字符串，其中有些是重復的，需要把重復的全部去掉，保留沒有重復的字符串。請怎么設計和實現？

3.一個文本文件，大約有一萬行，每行一個詞，要求統計出其中最頻繁出現的前10個詞，請給出思想，給出時間復雜度分析。

4.尋找熱門查詢：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。假設目前有一千萬個記錄，這些查詢串的重復讀比較高，雖然總數是1千萬，但是如果去除重復和，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就越熱門。請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。

后綴樹的應用：

1.查找字符串O是否在字符串S中。

方案：用S構造后綴樹，按在trie中搜索字串的方法搜索O即可。

原理：若O在S中，則O必然是S的某個后綴的前綴。

例如：leconte，查找O：con是否在S中，則O（con）必然是S（leconte）的前綴。

2.指定字符串T在字符串S中的重復次數。

方案：用S+’$’構造后綴樹，搜索T節點下的葉子節點數目即為重復次數

原理：如果T在S中重復了兩次，則S應有兩個后綴以T為前綴，重復次數自然統計出來了。

3.字符串S中的最長重復子串

方案：原理同2，具體做法是找到最深的非葉子節點。

這個深指從root所經歷過的字符個數，最深非葉子節點所經歷的字符串起來就是最長重復子串。為什么非要是葉子節點呢？因為既然是要重復的，當然葉子節點個數要>=2

4.兩個字符串S1,S2的最長公共子串（而非以前所說的最長公共子序列，因為子序列是不連續的，而子串是連續的。）

方案：將S1#S2$作為字符串壓入后綴樹，找到最深的非葉子節點，且該節點的葉子節點既有#也有$.

5.最長回文子串

轉載于:https://www.cnblogs.com/aiyelinglong/archive/2012/04/09/2439777.html

總結

以上是生活随笔為你收集整理的trie树和后缀树的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

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