什麼叫Trie樹?
Trie樹即字典樹。
又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用於統計，排序和保存大量的字符串（但不僅限於字符串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。 （以上來自百度百科，點這裡） 在我看來，Trie樹是一棵26叉樹（如果是統計字母的話），典型的空間換時間。那到底我們利用Trie來做什麼呢？ 1.統計單詞 2.匹配前綴 千篇一律地需要提到其性質： 1.根節點不包含字符，除根節點外的每一個子節點都只包含一個字符。 2.從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串 3.每個節點的所有子節點包含的字符都不相同。 而其效率主要體現，通過公共前綴盡可能減少查找復雜度。 下面，沒拍過字典樹的同學就跟著來練習吧！很快你就有感覺了。 首先，發一個模板，我是一個從開始學習語言就寫C++的人，所以我用了模板+類來寫，喜歡c風格的同學也可以看看其他人共享的模板。(感覺有點長～但是相對我覺得好理解，假設你知道並且喜歡用template.)
之後，怎麼少得了經典的問題呢？
HDU1251（統計難題）
http://acm.hdu.edu.cn/showproblem.php?pid=1251 字典樹做這些問題就是神器啊。注意統計的時候，node的處理，也就是insert和find的一些改變。HDU1671
http://acm.hdu.edu.cn/showproblem.php?pid=1671
HDU1075
http://acm.hdu.edu.cn/showproblem.php?pid=1075
這題目還是很赤裸的字典樹，但是我犯了一個小錯，讓我WA無數次。 AC的：（差別就在字符串copy 上沒有拷貝上'\0'……，也就是st[len]）
HDU1247 http://acm.hdu.edu.cn/showproblem.php?pid=1247 題目相對理解上會有點偏差,不是當且僅當兩個，是兩個，舉個例子 a abc b bc c 輸出的是:abc,bc(注意abc也是，不要因為abc=a+b+c，而忽略，只要可以滿足s=s1+s2即可，即abc=a+bc，bc=b+c)盡管我上面這個做法已經OK了，但是這是參考了別人，下面是我完全按自己想法寫的，程序員最高興的莫過於可以將自己的想法實現。
HDU1857,逆向思維的trie，可以參考我之前寫過的,點這裡
http://acm.hdu.edu.cn/showproblem.php?pid=1857
