首先說明一下字尾樹系列一共會有三篇文章，本文先介紹基本概念以及如何線性時間内構件字尾樹，第二篇文章會詳細介紹怎麼實作字尾樹（包含實作代碼），第三篇會着重談一談字尾樹的應用。
本文分為三個部分，
- 首先介紹一下字尾樹的“前身”-- trie樹以及字尾樹的概念；
- 然後介紹一下怎麼通過trie樹在平方時間内構件字尾樹；
- 最後介紹一下怎麼改進進而可以線上性時間内構件字尾樹；
一，從trie樹到字尾樹
在接觸字尾樹之前先簡單聊聊trie樹，也就是字典樹。trie樹有三個性質：
- 根節點不包含字元，除根節點外每一個節點都隻包含一個字元。
- 從根節點到某一節點，路徑上經過的字元連接配接起來，為該節點對應的字元串。
- 每個節點的所有子節點包含的字元都不相同。
将一系列字元串插入到trie樹的過程可以這樣來實作：首先，樹根不存任何字元；對于每個字元串，從左到右，沿着樹從根節點開始往下走直到找不到“路”可以走的時候，“自己開辟一條路”繼續往下走。比如往trie樹裡面存放ana ,ann ,ann, anna ,以及anne ,以及anne是個字元串的時候（注意一下，$是用來标志字元串末尾），我們會的到這樣一棵樹：見下左圖
上左圖這樣存儲的時候有點浪費。為了更高效我們把沒有分支的路徑壓縮，于是得到上右圖。很簡單吧
介紹完trie樹之後呢，我們再來看一看字尾，直接列出一個字元串MISSISSIPPI的所有字尾
1. MISSISSIPPI
2. ISSISSIPPI
3. SSISSIPPI
4. SISSIPPI
5. ISSIPPI
6. SSIPPI
7. SIPPI
8. IPPI
9. PPI
10. PI
11. I
而将這些字尾全部插入前面提到的trie樹中并壓縮，就得到字尾樹啦
二，兩種方法在平方時間内構件字尾樹
所謂的平方時間是指O(|T|*|T|)，|T|是指字元串的長度。
第一種方法非常顯然，就是直接按照字尾樹的定義來就可以了，将各個字尾依次插入trie樹中，再壓縮，總的時間複雜度顯然是平方級别的。
這裡給出的是另外一種方法。對照上面MISSISSIPPI的所有字尾，我們注意到第一種方法就是從左到右掃描完一個字尾再從上到下掃描所有的字尾。那麼另外一種思路就是，先安位對齊，然後從上到下掃描完每個位，再從左到右掃描下一位。舉個例子吧，第一種方法相當于先掃描完字尾１：MISSISSIPPI ，再往下掃描字尾２：ISSISSIPPI 以此類推；而第二種方法相當于從上到下先插入第一個字元M，然後再從上到下插入第二個字元I(有兩個)，然後再從上到下插入字元S(有三個)以此類推，參見下圖。
但是具體怎麼操作呢？因為顯然每次操作不能是簡簡單單的插入字元而已！
我們再後頭來看看上述過程，形式化一點，我們将原先的字元串表示為
T = t1t2 … tn$，其中ti表示第i個字元
Pi = t1t2 … ti ， i:th prefix of T
那麼，我們每次插入字元ti，相當于完成一個從Trie(Pi-1)到Trie(Pi)的過程，當所有字元插入完畢的時候我們整個字尾樹也就建構出來了。參見下圖：插入第二個字元b相當于完成了從Trie(a)到Trie(ab)的過程。。。。
那我們怎麼做呢？
上圖中也提示了，其實我們需要額外保留一個尾部連結清單，連接配接着目前的“尾部”節點－－也就是對應着Pi的一個字尾的那些個點。我們注意到尾部連結清單實際上是從表示T[0 .. i]字尾的點指向表示T[1 .. i]字尾的點再指向表示T[2 .. i]字尾的點，以此類推。
也可以看得出來，每次插入一個字元都需要周遊一下連結清單，第一次周遊的時候連結清單長度為1(就是根節點),第二次周遊的時候連結清單長度為2(點a,和根節點，參見Trie(a) )，以此類推，可知周遊的總複雜度是O(|T|*|T|)，建立連結清單也需要O(|T|*|T|)，後續壓縮Trie也需要O(|T|*|T|)，故而整個算法複雜度就是O(|T|*|T|)。
現在說明一下為什麼算法是正确的？Trie(Pi-1)存儲的是Pi-1的所有字尾，Trie(Pi)存儲的是Pi的所有字尾。Pi的字尾可以由Pi-1所有字尾後面插入字元ti，以及字尾ti所構成。那麼我們沿着Trie(Pi-1)尾部連結清單插入字元ti的過程也就是插入Pi的所有字尾的過程，所有算法是正确的。
但是，有沒有小失望，畢竟幹了這麼久發現跟第一種方法相比沒有收益（哭！）。
其實不用失望，我們做這麼多的目的在于通過改進，整個算法可以實作線性的，下面就一步步介紹這種改進算法。
三，改進第二種算法以實作線性時間建立字尾樹
1 直接在字尾樹上操作
首先一點我們必須直接在字尾樹上操作了，不能先建立Trie樹再壓縮，因為周遊Trie樹的複雜度就已經是平方級别了。
我們定義幾種節點：
- 葉節點： 出現在字尾樹葉子上的節點；
- 顯式節點：所有出現在字尾樹中的節點。顯然葉節點也是顯示節點；
- 内部節點：顯示節點中不是葉子節點的所有節點；
- 隐式節點：出現在Trie樹中但是沒有出現在字尾樹中的點；（因為路徑壓縮）
接下來我們來看看前面提到的尾部連結清單，尾部連結清單顯然包含了目前字尾樹中的葉節點以及部分的顯式/隐式節點。沿着尾部連結清單更新:
- 遇到葉子節點時隻需往葉子所在的邊上面的字元串後面插入字元就好了，不用改變樹的結構；
- 遇到顯式節點的時候，先看看插入的字元是否出現在顯式節點後緊跟的字元集合中（比如上圖中紅色的顯式節點後緊跟的字元集和就是｛s,p｝）,如果插入的字元出現在集合中，那麼什麼也不要做（是指不用改變樹的結構），因為已經存在了；如果沒有出現，在顯式節點後面增加一個葉子，邊上标注為這個字元。
- 遇到隐式節點時，一樣，先看看隐式節點後面的字元是不是目前将要插入的字元，如果有則不用管了，沒有則需要将目前隐式節點變為顯式節點，再增加新葉子。
我們用個例子來說明一下怎麼操作，為了便于說明隐式節點，我采用Trie樹表示：
從第三個圖到第四個圖，沿着尾部連結清單插入字元a，那麼連結清單第一個節點為葉節點，故而直接在邊上插入這個字元就好了；連結清單第二個節點還是葉子，在邊上插入字元就好了；第三個節點是隐式節點，看看緊跟着隐式節點後面的字元，不是a，故而将這個隐式節點變為顯式節點，再增加一個葉子；第四個是顯式節點（根節點），其緊跟的字元集和為{a,b}，a出現在這個集合中，故而不用改變結構了。當然了，連結清單還是要維護的啊，Ｏ（∩＿∩）Ｏ哈哈～
好了，到此，我們實作了直接在字尾樹上操作而完全撇開Trie樹了，小有進步啦，～＼（≧▽≦）／～啦啦啦
現在開始優化啦！
2. 自動更新葉節點
首先一點，在字尾樹上直接操作的時候，邊上的字元串就沒必要直接存儲啦，我們可以存這個字元串對于在原先總的字元串T中的坐标。如上方右邊那個圖就是将左邊第四個圖，壓縮之後得到的字尾樹。[2,4]就表示baa。
這樣一來啊，存儲字尾樹的空間就大大減小了。
接着，我們來看一下啊，字尾樹S(Pi-1)中的葉子節點在S(Pi)中也是葉子節點，也就是說”一朝為葉，終身為葉“。而且我們還可以注意到尾部連結清單的前半部分全是葉子。也就是說如果S(Pi)有k個葉子，那麼表示T[0 .. i]，……，T[k-1 .. i]字尾的點全是葉子。
我們首先來看一下什麼時候字尾會不在葉子上：T[j .. i-1]不在S(Pi-1)葉子上，表明代表該字尾的點之後還有點存在，也就是說T[0 .. i-1]中存在子串S=T[j .. i-1] + c’ ，其中c'不為空。注意一下這是充分必要條件，因為葉子節點後面是不可能還存在點的。
現在我們來證明一下：（ti加入到 S(Pi-1) 的過程）
-
- 首先，T[0 .. i-1]肯定在葉子上。為什麼呢，因為在S(Pi-1)中T[0 .. i-1]是最長的，如果它不在葉子上，那麼必然存在比T[0 - i-1]還長的串，沖突，故而T[0 .. i-1]一定在葉子上。
- 其次，對于任何 j < i-1， 如果 T[j .. i-1] 不在樹葉上，那麼 T[j+1 .. i-1] 更不可能在樹葉上；為什麼呢，因為T[j .. i-1]不在葉子上表明T[0 .. i-1]中存在子串S=T[j .. i-1] + c’ ，其中c'不為空。那麼T[0 .. i-1]中y也必然存在子串S‘=T[j+1 .. i-1] + c’，因為S’是S的字尾。故而 T[j+1 .. i-1]也不在葉子上
- 于是我們知道k個葉子一定是T[0 .. i]，……，T[k-1 .. i]
我們來利用一下上述性質。葉節點每次更新都是把ti插入到葉子所在邊的字尾字元串中，是以表示字元串的區間就變成了[ , ｉ]。那麼我們還有必要每次都沿着尾部連結清單去更新麼？
我們可以這樣，将葉子那個邊上的表示字元串的區間用[ , #]來表示，#表示目前插入字元在T中的下标。那麼這樣一來，葉子節點就自動更新啦。
再利用第二個性質，我們完全就可以不管尾部連結清單的前k個節點啦。
這是又一大進步！
咱們接着來！
3. 當新字尾出現在原先字尾樹中
我們來看，根據沿尾部連結清單更新的算法，無論是顯式節點還是隐式節點，當帶插入字元ti出現在節點的緊跟字元集合的時候，我們就不用管了。也就是說如果T[j .. i]出現在S(Pi-1)，也就是S(T[0 .. i-1])，中的時候，我們就不用改變樹的結構了（當然需要還調整一些參數）。
我們再來看，對于任何 j < i-1，如果T[j .. i]出現在S(T[0 .. i-1])中，那麼T[j+1 .. i]也必然出現在S(T[0 .. i-1])中。下面給出證明：
- 首先我們知道T[0..i-1] 的所有字尾都在字尾樹中。
- 其次，T[0..i-1] 的任意子串都可以表示為它的某一個字尾的字首。
- 是以 T[0..i-1] 的所有子串都在字尾樹中。
- T[j+1 .. i] 是 T[j..i] 的子串， T[j..i] 又是 T[0..i-1] 的子串（因為T[j .. i]出現在S(T[0 .. i-1])中），是以 T[j+1 .. i] 也是 T[0..i-1] 的子串。
- 是以字尾樹中存在 T[j+1 .. i]
這也就是說如果尾部連結清單中某一個節點所代表的字尾加上ti，也就是T[j .. i]，出現在S(T[0 .. i-1])中,那麼連結清單後面的所有節點代表的字尾加上ti也都出現在S(T[0 .. i-1])中。
故而所有這些點，無論是顯式還是隐式節點都可以不用管了。
這又是一個大優化！
綜合上面兩個優化，我們知道事實上我們隻需要處理原先尾部連結清單的中間一段節點就可以了，對于這些節點而言，每處理一次必定增加一個新葉子（為什麼呢，因為這些節點既不是葉子節點，又不滿足顯或是隐式節點不用增加葉子的條件）。而”一朝為葉，終身為葉“，我們最終的字尾樹S(T[0 .. n])隻有n個葉子(其中tn= )。（為什麼呢，因為不可能存在子串S=T[j..n]+c ′ ，因為這要求子串中 )。（為什麼呢，因為不可能存在子串S=T[j..n]+c′，因為這要求子串中之後還有字元，這是辦不到的），這也就是說整個建樹過程中我們一共隻需要在尾部連結清單上處理n次就可以了，這是一個好兆頭！
種種迹象表明我們快到O(|T|)時間了，哈哈，原理就先說這麼多了。能不能實作最終的線性時間，就看下一節－－線性時間内建構字尾樹！
四 引用
１. http://www.cnblogs.com/snowberg/archive/2011/10/21/2468588.html
2. http://blog.csdn.net/v_july_v/article/details/6897097
3. On–line construction of suffix trees
轉載位址：
http://www.cnblogs.com/xubenben/p/3484988.html