前面的文章中有講解了模式比對相關的KMP和TrieTree，他們有各自的方式去提高性能，進而也應用在不同的場景中，這一次我們講解字尾樹（SuffixTree），相信如果沒有專門去看過這些知識的同學應該很少知道字尾樹，那麼字尾樹到底是什麼，他能解決什麼樣的問題呢？
字尾樹（SuffixTree）一種資料結構，通過對一個字元串所有字尾操作建構一棵樹，可以支援字元串的快速比對查詢，他對于以下幾個字元串問題可以做到快速實作。
1> 查找字元串A是否在字元串B中，也就是正常的字元串查找問題。
2> 計算給定的字元串A在字元串B中重複出現的次數。也就是子串重複的次數。
3> 查找字元串A的最長重複子串。
4> 查找字元串A和字元串B的最長公共子串。不是LCS問題哦！
5> 查找字元串A的最長回文子串。
6> 其實SuffixTree最常用的地方是生物學的堿基配對問題.
那看了上述問題，我們來講解字尾樹的結構，字尾樹顧名思義是要用到字元串的字尾，先來說明下什麼是字尾，比如有一個字元串dream，那麼他的字尾有很多個，分别是dream它本身，ream，eam，am，m，還有一個空字元串當然也是他的字尾。他的字尾集合為：dream=suffix{dream, ream, eam, am,m,空串}。我們建構一個字尾樹就要利用到這些字尾來建構一壓縮的trie樹，也就是Compacted Trie(将trie上單個子節點的路徑進行壓縮即可得到)。
先看一個CompactedTrie的建構。假設我們的有字元串abc, abd, def我們首先用這些字元串建構一個Trie如下所示：
我們發現對于單純的Trie每個邊都是存放了一個單個字元，在空間上有些浪費，我們講單個子節點的邊都進行壓縮存儲在一起，如下圖所示就變成了一棵壓縮字典樹(CompactedTrie).
字尾樹（SuffixTree）其實是一棵被壓縮過的TrieTree，也就是CompactedTrie，隻不過字尾樹中存儲的關鍵字都是字元串的字尾，通過将一個字元串的字尾集合構造成一個TrieTree，然後在進行路徑壓縮，變得到了一顆字尾樹，對于deaabd所實作的字尾樹如下所示：
這樣我們就得到了建構字尾樹的抽象構造過程：首先根據文本字元串生成字元串字尾的集合；其次将每個字尾作為一個單獨的關鍵詞，建構一棵 CompactedTrie。
看到這樣一棵樹我們就明白字尾樹到底是什麼形态的了，如果你想查找某個字元串是不是子串從根節點開始按照樹的結構從上到下比對就可以了，因為如果一個字元串A是兩外一個字元串B的子串，那麼這個字元串A必定是字元串B的某個字尾的字首。認識了字尾樹的形态，那麼很容易就會清楚字尾樹的查找效率為O(m) m為需要查找的串的長度，這個速度已經相當快了，但是大家很容易就會發現，真正消耗時間的是在建構一顆字尾樹，字尾樹需要字元串進行預處理進而進行字尾樹的構造。這也是最複雜最難的部分，主流的字尾樹構造算法有兩種時間複雜度，一種是建構是基于O(n^2)時間複雜度的暴力構造，當然對于時間要求和資料量小的情況這種完全也可以，另外一種是非常出名的線性時間構造也就是UKKonen的加速構造。這裡我們先介紹最簡單的構造方法，剩下的優化留作後面文章單獨進行講解。
暴力構造字尾樹是比較簡單了解也最容易實作的一種，時間複雜度是O(n^2)，也就是我們上文中進行介紹的
trie—>compacted-àsuffix的方法。構造過程如下：
1> 首先求出字元串A的所有字尾，即字尾集合。
2> 使用字尾集合進行構造一棵Trie樹。
3> 對trie樹進行路徑壓縮，即得到suffix trie
下一篇文章我們講介紹線性時間構造字尾樹的方法，方法有些複雜，而且後面的文章我們還會陸續推出其他字元串模式比對的算法，BM，AC自動機，EKMP，字尾數組等等
現在來先說明一開始講解的SuffixTrie解決問題的方案
1. 查找字元串A是否在字元串B中，也就是正常的字元串查找問題。
用B構造字尾樹，按在trie中搜尋字串的方法搜尋A即可。若A在B中，A肯定是B的一個字尾的字首
2. 計算給定的字元串A在字元串B中重複出現的次數。也就是子串重複的次數。
用B+#的形式建構字尾樹，查找A節點下的葉子節點的個數即為重複次數， 如果A在B中重複了3次，那麼B重肯定有三個字尾的以A為字首。
3. 查找字元串A的最長重複子串。
最深的非葉子節點所經曆的字元串起來就是最長的重複子串，因為如果是重複的葉子節點必須大于1
4.查找字元串A和字元串B的最長公共子串
用[email protected]#作為字元串壓入字尾樹，找到最深的非葉子節點，并且該節點的葉子節點即有@也有#即可。最深的葉子節點是指從root所經曆過的字元的個數
5.最長回文子串
我們将字元串A進行翻轉得到字元串B，用字元串A和字元串B建構廣義字尾樹（廣義字尾樹傳統的字尾樹處理一坨單詞的所有字尾。廣義字尾樹存儲任意多個單詞的所有字尾），進而最長的回文字元串就是字元串A和B的LCA（最長公共祖先）
預處理字尾樹，使得查詢LCA的複雜度為O(1)。這步的開銷是O(N)，N是單詞S的長度
對單詞的每一位置i(也就是從0到N-1)，擷取LCA(A(i), B(N-i+1)) 以及LCA(A(i+1),B(n-i+1))。查找兩次的原因是我們需要考慮奇數回文和偶數回文的情況。這步要考察每坨i，是以複雜度是O(N)
找到最大的LCA，我們也就得到了回文的中心i以及回文的半徑長度，自然也就得到了最長回文。總的複雜度O(n)。