Suffix Trie ： 又稱后綴Trie或后綴樹。它與Trie樹的最大不同在于，后綴Trie的字符串集合是由指定字符串的后綴子串構成的。比如、完整字符串"minimize"的后綴子串組成的集合S分別如下：

?

???????? s1=minimize

???????? s2=inimize

???????? s3=nimize

???????? s4=imize

???????? s5=mize

???????? s6=ize

???????? s7=ze

???????? s8=e

?

????? 然后把這些子串的公共前綴作為內部結點構成一棵"minimize"的后綴樹，如圖所示，其中上圖是Trie樹的字符表示，下圖是壓縮表示(詳細見《 Trie樹 》)。 可見Suffic Trie是一種很適合操作字符串子串的數據結構。 它和PAT tree在這一點上類似。

?

?

Suffix Trie的創建?

?

????? 標準Tire樹的每一個內部結點只有一個字符，也就是說公共前綴每一次只找一個。而Suffix Trie的公共前綴可以是多個字符，因此在創建Suffix Trie的時候，每插入一個后綴子串，就可能對內部結點造成一次分類。下面我們我們看一種后綴樹構造算法。以"minimize"為例：

?

????? 當插入子串時，發現葉子結點中的關鍵字與子串有公共前綴，則需要將該葉子結點分裂。如上圖第3到4步。否則，重新創建一個葉子結點來存放后綴，如上圖第1到2步

?

Suffix Trie的子串查詢

?

???? 如果在后綴樹T中查找子串P，我們需要這樣的過程：

???? (1) 從根結點root出發，遍歷所有的根的孩子結點：N1,N2,N3....

???? (2) 如果所有孩子結點中的關鍵字的第一個字符都和P的第一個字符不匹配，則沒有這個子串，查找結束。

???? (3) 假如N3結點的關鍵字K3第一個字符與P的相同，則匹配K3和P。

????????? 若 K3.length>=P.length? 并且K3.subString(0,P.length-1)=P，則匹配成功，否則匹配失敗。

????????? 若 K3.length<=P.length? 并且K3=P.subString(0, K3.length-1)，則將子串P1=P.subString(K3.length, P.length); 即取出P中排除K3之后的子串。然后P1以N3為根結點繼續重復(1)~(3)的步驟。直到匹配完P1的所有字符，則匹配成功。否則匹配失敗。

?

????? 查詢效率：很顯然，在上面的算法中。匹配成功正好比較了P.length次字符。而定位結點的孩子指針，和Trie情況類似，假如字母表數量為d。則查詢效率為O(d*m)，實際上，d是固定常數，如果使用Hash表直接定位，則d=1.

????? 因此，后綴樹查詢子串P的時間復雜度為O(m)，其中m為P的長度。

?

Suffix Trie的應用

?

????? 標準Trie樹只適合前綴匹配和全字匹配，并不適合 后綴和子串匹配。而后綴樹在這方面則非常合適。

?

????? 另外 后綴樹也可以進行前綴匹配。 如果模式串P是字符串S的前綴的話，那么從根結點出發遍歷后綴樹，一定能夠尋找到一條路徑完全匹配完P。比如上圖： 模式串P=“mini”，主串S="minimize"。P從根節點出發，首先匹配到結點mi，然后再匹配孩子結點nimize。直到P中所有的字符都找到為止。所以P是S的前綴。

?

?

【串和序列處理 4】Suffix Trie 子串匹配結構