什麼叫trie樹?
trie樹即字典樹。
又稱單詞查找樹，，是一種，是一種哈希樹的變種。典型應用是用于統計，排序和儲存大量的串（但不僅限于字元串），是以經常被搜尋引擎系統用于文本詞頻統計。它的優點是：利用字元串的公共字首來減少查詢時間，最大限度地減少無謂的字元串比較，查詢效率比高。
（以上來自百度百科，點）
在我看來，trie樹是一棵26叉樹（如果是統計字母的話），典型的空間換時間。那到底我們利用trie來做什麼呢？
1.統計單詞
2.比對字首
千篇一律地需要提到其性質：
1.根節點不包含字元，除根節點外的每一個子節點都隻包含一個字元。
2.從根節點到某一節點，路徑上經過的字元連接配接起來，為該節點對應的字元串
3.每個節點的所有子節點包含的字元都不相同。
而其效率主要展現，通過公共字首盡可能減少查找複雜度。
下面，沒拍過字典樹的同學就跟着來練習吧！很快你就有感覺了。
首先，發一個模闆，我是一個從開始學習語言就寫c++的人，是以我用了模闆+類來寫，喜歡c風格的同學也可以看看其他人共享的模闆。(感覺有點長～但是相對我覺得好了解，假設你知道并且喜歡用template.)
view code
之後，怎麼少得了經典的問題呢？
hdu1251（統計難題）
字典樹做這些問題就是神器啊。注意統計的時候，node的處理，也就是insert和find的一些改變。
hdu1671
hdu1004，或許你用map水過去了，但是你不妨試試用字典樹擷取0ms吧！
hdu1075
這題目還是很赤裸的字典樹，但是我犯了一個小錯，讓我wa無數次。
ac的：
wa的：
（差别就在字元串copy 上沒有拷貝上‘\0‘……，也就是st[len]）
hdu1247
題目相對了解上會有點偏差,不是當且僅當兩個，是兩個，舉個例子
a
abc
b
bc
c
輸出的是:abc,bc(注意abc也是，不要因為abc=a+b+c，而忽略，隻要可以滿足s=s1+s2即可，即abc=a+bc，bc=b+c)
盡管我上面這個做法已經ok了，但是這是參考了别人，下面是我完全按自己想法寫的，程式員最高興的莫過于可以将自己的想法實作。
hdu1857,逆向思維的trie，可以參考我之前寫過的,點