后綴樹 - gaochundong－IT工程師數位筆記本

文章出處

在《字符串匹配算法》一文中，我們熟悉了字符串匹配問題的形式定義：

文本（Text）是一個長度為 n 的數組 T[1..n]；
模式（Pattern）是一個長度為 m 且 m≤n 的數組 P[1..m]；
T 和 P 中的元素都屬于有限的字母表 Σ 表；
如果 0≤s≤n-m，并且 T[s+1..s+m] = P[1..m]，即對 1≤j≤m，有 T[s+j] = P[j]，則說模式 P 在文本 T 中出現且位移為 s，且稱 s 是一個有效位移（Valid Shift）。

比如上圖中，目標是找出所有在文本 T = abcabaabcabac 中模式 P = abaa 的所有出現。該模式在此文本中僅出現一次，即在位移 s = 3 處，位移 s = 3 是有效位移。

解決字符串匹配問題的常見算法有：

字符串匹配算法通常分為兩個步驟：預處理（Preprocessing）和匹配（Matching）。所以算法的總運行時間為預處理和匹配的時間的總和。下圖描述了常見字符串匹配算法的預處理和匹配時間。

我們知道，上述字符串匹配算法均是通過對模式（Pattern）字符串進行預處理的方式來加快搜索速度。對 Pattern 進行預處理的最優復雜度為 O(m)，其中 m 為 Pattern 字符串的長度。那么，有沒有對文本（Text）進行預處理的算法呢？本文即將介紹一種對 Text 進行預處理的字符串匹配算法：后綴樹（Suffix Tree）。

后綴樹的性質：

存儲所有 n(n-1)/2 個后綴需要 O(n) 的空間，n 為的文本（Text）的長度；
構建后綴樹需要 O(dn) 的時間，d 為字符集的長度（alphabet）；
對模式（Pattern）的查詢需要 O(dm) 時間，m 為 Pattern 的長度；

在《字典樹》一文中，介紹了一種特殊的樹狀信息檢索數據結構：字典樹（Trie）。Trie 將關鍵詞中的字符按順序添加到樹中的節點上，這樣從根節點開始遍歷，就可以確定指定的關鍵詞是否存在于 Trie 中。

下面是根據集合 {bear, bell, bid, bull, buy, sell, stock, stop} 所構建的 Trie 樹。

我們觀察上面這顆 Trie，對于關鍵詞 "bear"，字符 "a" 和 "r" 所在的節點沒有其他子節點，所以可以考慮將這兩個節點合并，如下圖所示。

這樣，我們就得到了一棵壓縮過的 Trie，稱為壓縮字典樹（Compressed Trie）。

而后綴樹（Suffix Tree）則首先是一棵 Compressed Trie，其次，后綴樹中存儲的關鍵詞為所有的后綴。這樣，實際上我們也就得到了構建后綴樹的抽象過程：

根據文本 Text 生成所有后綴的集合；
將每個后綴作為一個單獨的關鍵詞，構建一棵 Compressed Trie。

A suffix tree is a compressed trie for all the suffixes of a text.

比如，對于文本 "banana\0"，其中 "\0" 作為文本結束符號。下面是該文本所對應的所有后綴。

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

將每個后綴作為一個關鍵詞，構建一棵 Trie。

然后，將獨立的節點合并，形成 Compressed Trie。

則上面這棵樹就是文本 "banana\0" 所對應的后綴樹。

現在我們先熟悉兩個概念：顯式后綴樹（Explicit Suffix Tree）和隱式后綴樹（Implicit Suffix Tree）。

下面用字符串 "xabxa" 舉例說明兩者的區別，其包括后綴列表如下。

xabxa
abxa
bxa
xa
a

我們發現，后綴 "xa" 和 "a" 已經分別包含在后綴 "xabxa" 和 "abxa" 的前綴中，這樣構造出來的后綴樹稱為隱式后綴樹（Implicit Suffix Tree）。

而如果不希望這樣的情形發生，可以在每個后綴的結尾加上一個特殊字符，比如 "$" 或 "#" 等，這樣我們就可以使得后綴保持唯一性。

xabxa$
abxa$
bxa$
xa$
a$
$

在 1995 年，Esko Ukkonen 發表了論文《On-line construction of suffix trees》，描述了在線性時間內構建后綴樹的方法。下面嘗試描述 Ukkonen 算法的基本實現原理，從簡單的字符串開始描述，然后擴展到更復雜的情形。

Suffix Tree 與 Trie 的不同在于，邊（Edge）不再只代表單個字符，而是通過一對整數 [from, to] 來表示。其中 from 和 to 所指向的是 Text 中的位置，這樣每個邊可以表示任意的長度，而且僅需兩個指針，耗費 O(1) 的空間。

首先，我們從一個最簡單的字符串 Text = "abc" 開始實踐構建后綴樹，"abc" 中沒有重復字符，使得構建過程更簡單些。構建過程的步驟是：從左到右，對逐個字符進行操作。

abc

第 1 個字符是 "a"，創建一條邊從根節點（root）到葉節點，以 [0, #] 作為標簽代表其在 Text 中的位置從 0 開始。使用 "#" 表示末尾，可以認為 "#" 在 "a" 的右側，位置從 0 開始，則當前位置 "#" 在 1 位。

其代表的后綴意義如下。

第 1 個字符 "a" 處理完畢，開始處理第 2 個字符 "b"。涉及的操作包括：

擴展已經存在的邊 "a" 至 "ab"；
插入一條新邊以表示 "b"；

其代表的后綴意義如下。

這里，我們觀察到了兩點：

"ab" 邊的表示 [0, #] 與之前是相同的，當 "#" 位置由 1 挪至 2 時，[0, #] 所代表的意義自動地發生了改變。
每條邊的空間復雜度為 O(1)，即只消耗兩個指針，而與邊所代表的字符數量無關；

接著再處理第 3 個字符 "c"，重復同樣的操作，"#" 位置向后挪至第 3 位：

其代表的后綴意義如下。

此時，我們觀察到：

經過上面的步驟后，我們得到了一棵正確的后綴樹；
操作步驟的數量與 Text 中的字符的數量一樣多；
每個步驟的工作量是 O(1)，因為已存在的邊都是依據 "#" 的挪動而自動更改的，僅需為最后一個字符添加一條新邊，所以時間復雜度為 O(1)。則，對于一個長度為 n 的 Text，共需要 O(n) 的時間構建后綴樹。

當然，我們進展的這么順利，完全是因為所操作的字符串 Text = "abc" 太簡單，沒有任何重復的字符。那么現在我們來處理一個更復雜一些的字符串 Text = "abcabxabcd"。

abcabxabcd

同上面的例子類似的是，這個新的 Text 同樣以 "abc" 開頭，但其后接著 "ab","x","abc","d" 等，并且出現了重復的字符。

前 3 個字符 "abc" 的操作步驟與上面介紹的相同，所以我們會得到下面這顆樹：

當 "#" 繼續向后挪動一位，即第 4 位時，隱含地意味著已有的邊會自動的擴展為：

即 [0, #], [1, #], [2, #] 都進行了自動的擴展。按照上面的邏輯，此時應該為剩余后綴 "a" 創建一條單獨的邊。但，在做這件事之前，我們先引入兩個概念。

活動點（active point），是一個三元組，包括（active_node, active_edge, active_length）；
剩余后綴數（remainder），是一個整數，代表著還需要插入多少個新的后綴；

如何使用這兩個概念將在下面逐步地說明。不過，現在我們可以先確定兩件事：

在 Text = "abc" 的例子中，活動點（active point）總是 (root, '\0x', 0)。也就是說，活動節點（active_node）總是根節點（root），活動邊（active_edge）是空字符 '\0x' 所指定的邊，活動長度（active_length）是 0。
在每個步驟開始時，剩余后綴數（remainder）總是 1。意味著，每次我們要插入的新的后綴數目為 1，即最后一個字符。

# = 3, active_point = (root, '\0x', 1), remainder = 1

當處理第 4 字符 "a" 時，我們注意到，事實上已經存在一條邊 "abca" 的前綴包含了后綴 "a"。在這種情況下：

我們不再向 root 插入一條全新的邊，也就是 [3, #]。相反，既然后綴 "a" 已經被包含在樹中的一條邊上 "abca"，我們保留它們原來的樣子。
設置 active point 為 (root, 'a', 1)，也就是說，active_node 仍為 root，active_edge 為 'a'，active_length 為 1。這就意味著，活動點現在是從根節點開始，活動邊是以 'a' 開頭的某個邊，而位置就是在這個邊的第 1 位。這個活動邊的首字符為 'a'，實際上，僅會有一個邊是以一個特定字符開頭的。
remainder 的值需要 +1，也就是 2。

# = 4, active_point = (root, 'a', 1), remainder = 2

此時，我們還觀察到：當我們要插入的后綴已經存在于樹中時，這顆樹實際上根本就沒有改變，我們僅修改了 active point 和 remainder。那么，這顆樹也就不再能準確地描述當前位置了，不過它卻正確地包含了所有的后綴，即使是通過隱式的方式（Implicitly）。因此，處理修改變量，這一步沒有其他工作，而修改變量的時間復雜度為 O(1)。

繼續處理下一個字符 "b"，"#" 繼續向后挪動一位，即第 5 位時，樹被自動的更新為：

由于剩余后綴數（remainder）的值為 2，所以在當前位置，我們需要插入兩個最終后綴 "ab" 和 "b"。這是因為：

前一步的 "a" 實際上沒有被真正的插入到樹中，所以它被遺留了下來（remained），然而我們又向前邁了一步，所以它現在由 "a" 延長到 "ab"；
還有就是我們需要插入新的最終后綴 "b"；

實際操作時，我們就是修改 active point，指向 "a" 后面的位置，并且要插入新的最終后綴 "b"。但是，同樣的事情又發生了，"b" 事實上已經存在于樹中一條邊 "bcab" 的前綴上。那么，操作可以歸納為：

修改活動點為 (root, 'a', 2)，實際還是與之前相同的邊，只是將指向的位置向后挪到 "b"，修改了 active_length，即 "ab"。
增加剩余后綴數（remainder）為 3，因為我們又沒有為 "b" 插入全新的邊。

# = 5, active_point = (root, 'a', 2), remainder = 3

再具體一點，我們本來準備插入兩個最終后綴 "ab" 和 "b"，但因為 "ab" 已經存在于其他的邊的前綴中，所以我們只修改了活動點。對于 "b"，我們甚至都沒有考慮要插入，為什么呢？因為如果 "ab" 存在于樹中，那么他的每個后綴都一定存在于樹中。雖然僅僅是隱含性的，但卻一定存在，因為我們一直以來就是按照這樣的方式來構建這顆樹的。

繼續處理下一個字符 "x"，"#" 繼續向后挪動一位，即第 6 位時，樹被自動的更新為：

由于剩余后綴數（Remainder）的值為 3，所以在當前位置，我們需要插入 3 個最終后綴 "abx", "bx" 和 "x"。

活動點告訴了我們之前 "ab" 結束的位置，所以僅需跳過這一位置，插入新的 "x" 后綴。"x" 在樹中還不存在，因此我們分裂 "abcabx" 邊，插入一個內部節點：

分裂和插入新的內部節點耗費 O(1) 時間。

現在，我們已經處理了 "abx"，并且把 remainder 減為 2。然后繼續插入下一個后綴 "bx"，但做這個操作之前需要先更新活動點，這里我們先做下部分總結。

對于上面對邊的分裂和插入新的邊的操作，可以總結為 Rule 1，其應用于當 active_node 為 root 節點時。

Rule 1

當向根節點插入時遵循：

active_node 保持為 root；

active_edge 被設置為即將被插入的新后綴的首字符；

active_length 減 1；

因此，新的活動點為 (root, 'b', 1)，表明下一個插入一定會發生在邊 "bcabx" 上，在 1 個字符之后，即 "b" 的后面。

# = 6, active_point = (root, 'b', 1), remainder = 2

我們需要檢查 "x" 是否在 "b" 后面出現，如果出現了，就是我們上面見到過的樣子，可以什么都不做，只更新活動點。如果未出現，則需要分裂邊并插入新的邊。

同樣，這次操作也花費了 O(1) 時間。然后將 remainder 更新為 1，依據 Rule 1 活動點更新為 (root, 'x', 0)。

# = 6, active_point = (root, 'x', 0), remainder = 1

此時，我們將歸納出 Rule 2。

Rule 2

如果我們分裂（Split）一條邊并且插入（Insert）一個新的節點，并且如果該新節點不是當前步驟中創建的第一個節點，則將先前插入的節點與該新節點通過一個特殊的指針連接，稱為后綴連接（Suffix Link）。后綴連接通過一條虛線來表示。

繼續上面的操作，插入最終后綴 "x"。因為活動點中的 active_length 已經降到 0，所以插入操作將發生在 root 上。由于沒有以 "x" 為前綴的邊，所以插入一條新的邊：

這樣，這一步驟中的所有操作就完成了。

# = 6, active_point = (root, '\0x', 0), remainder = 1

繼續處理下一個字符 "a"，"#" 繼續向后挪動一位。發現后綴 "a" 已經存在于數中的邊中，所以僅更新 active point 和 remainder。

# = 7, active_point = (root, 'a', 1), remainder = 2

繼續處理下一個字符 "b"，"#" 繼續向后挪動一位。發現后綴 "ab" 和 "b" 都已經存在于樹中，所以僅更新 active point 和 remainder。這里我們先稱 "ab" 所在的邊的節點為 node1。

# = 8, active_point = (root, 'a', 2), remainder = 3

繼續處理下一個字符 "c"，"#" 繼續向后挪動一位。此時由于 remainder = 3，所以需要插入 "abc","bc","c" 三個后綴。"c" 實際上已經存在于 node1 后的邊上。

# = 9, active_point = (node1, 'c', 1), remainder = 4

繼續處理下一個字符 "d"，"#" 繼續向后挪動一位。此時由于 remainder = 4，所以需要插入 "abcd","bcd","cd","d" 四個后綴。

上圖中的 active_node，當節點準備分裂時，被標記了紅色。則歸納出了 Rule 3。

Rule 3

當從 active_node 不為 root 的節點分裂邊時，我們沿著后綴連接（Suffix Link）的方向尋找節點，如果存在一個節點，則設置該節點為 active_noe；如果不存在，則設置 active_node 為 root。active_edge 和 active_length 保持不變。

所以，現在活動點為 (node2, 'c', 1)，其中 node2 為下圖中的紅色節點：

# = 10, active_point = (node2, 'c', 1), remainder = 3

由于對 "abcd" 的插入已經完成，所以將 remainder 的值減至 3，并且開始處理下一個剩余后綴 "bcd"。此時需要將邊 "cabxabcd" 分裂，然后插入新的邊 "d"。根據 Rule 2，我們需要在之前插入的節點與當前插入的節點間創建一條新的后綴連接。

此時，我們觀察到，后綴連接（Suffix Link）讓我們能夠重置活動點，使得對下一個后綴的插入操作僅需 O(1) 時間。從上圖也確認了，"ab" 連接的是其后綴 "b"，而 "abc" 連接的是其后綴 "bc"。

當前操作還沒有完成，因為 remainder 是 2，根絕 Rule 3 我們需要重新設置活動點。因為上圖中的紅色 active_node 沒有后綴連接（Suffix Link），所以活動點被設置為 root，也就是 (root, 'c', 1)。

# = 10, active_point = (root, 'c', 1), remainder = 2

因此，下一個插入操作 "cd" 將從 Root 開始，尋找以 "c" 為前綴的邊 "cabxabcd"，這也引起又一次分裂：

由于此處又創建了一個新的內部節點，依據 Rule 2，我們需要建立一條與前一個被創建內節點的后綴連接。

然后，remainder 減為 1，active_node 為 root，根據 Rule 1 則活動點為 (root, 'd', 0)。也就是說，僅需在根節點上插入一條 "d" 新邊。

# = 10, active_point = (root, 'd', 0), remainder = 1

整個步驟完成。

總體上看，我們有一系列的觀察結果：

在每一步中將 "#" 向右移動 1 位時，所有葉節點自動更新的時間為 O(1)；
但實際上并沒有處理這兩種情況：
- 從前一步中遺留的后綴；
- 當前步驟中的最終字符；
remainder 告訴了我們還余下多少后綴需要插入。這些插入操作將逐個的與當前位置 "#" 之前的后綴進行對應，我們需要一個接著一個的處理。更重要的是，每次插入需要 O(1) 時間，活動點準確地告訴了我們改如何進行，并且也僅需在活動點中增加一個單獨的字符。為什么？因為其他字符都隱式地被包含了，要不也就不需要 active point 了。
每次插入之后，remainder 都需要減少，如果存在后綴連接（Suffix Link）的話就續接至下一個節點，如果不存在則返回值 root 節點（Rule 3）。如果已經是在 root 節點了，則依據 Rule 1 來修改活動點。無論哪種情況，僅需 O(1) 時間。
如果這些插入操作中，如果發現要被插入的字符已經存在于樹中，則什么也不做，即使 remainder > 0。原因是要被插入的字符實際上已經隱式地被包含在了當前的樹中。而 remainder > 0 則確保了在后續的操作中會進行處理。
那么如果在算法結束時 remainder > 0 該怎么辦？這種情況說明了文本的尾部字符串在之前某處已經出現過。此時我們需要在尾部添加一個額外的從未出現過的字符，通常使用 "$" 符號。為什么要這么做呢？如果后續我們用已經完成的后綴樹來查找后綴，匹配結果一定要出現在葉子節點，否則就會出現很多假匹配，因為很多字符串已經被隱式地包含在了樹中，但實際并不是真正的后綴。同時，最后也強制 remainder = 0，以此來保證所有的后綴都形成了葉子節點。盡管如此，如果想用后綴樹搜索常規的子字符串，而不僅是搜索后綴，這么做就不是必要的了。
那么整個算法的復雜度是多少呢？如果 Text 的長度為 n，則有 n 步需要執行，算上 "$" 則有 n+1 步。在每一步中，我們要么什么也不做，要么執行 remainder 插入操作并消耗 O(1) 時間。因為 remainder 指示了在前一步中我們有多少無操作次數，在當前步驟中每次插入都會遞減，所以總體的數量還是 n。因此總體的復雜度為 O(n)。
然而，還有一小件事我還沒有進行適當的解釋。那就是，當我們續接后綴連接時，更新 active point，會發現 active_length 可能與 active_node 協作的并不好。例如下面這種情況：

假設 active point 是紅色節點 (red, 'd', 3)，因此它指向 "def" 邊中 "f" 之后的位置。現在假設我們做了必要的更新，而且依據 Rule 3 續接了后綴連接并修改了活動點，新的 active point 是 (green, 'd', 3)。然而從綠色節點出發的 "d" 邊是 "de"，這條邊只有 2 個字符。為了找到合適的活動點，看起來我們需要添加一個到藍色節點的邊，然后重置活動點為 (blue, 'f', 1)。

在最壞的情況下，active_length 可以與 remainder 一樣大，甚至可以與 n 一樣大。而恰巧這種情況可能剛好在找活動點時發生，那么我們不僅需要跳過一個內部節點，可能是多個節點，最壞的情況是 n 個。由于每步里 remainder 是 O(n)，續接了后綴連接之后的對活動點的后續調整也是 O(n)，那么是否意味著整個算法潛在需要 O(n²) 時間呢？

我認為不是。理由是如果我們確實需要調整活動點（例如，上圖中從綠色節點調整到藍色節點），那么這就引入了一個擁有自己的后綴連接的新節點，而且 active_length 將減少。當我們沿著后綴連接向下走，就要插入剩余的后綴，且只是減少 active_length，使用這種方法可調整的活動點的數量不可能超過任何給定時刻的 active_length。由于 active_length 從來不會超過 remainder，而 remainder 不僅在每個單一步驟里是 O(n)，而且對整個處理過程進行的 remainder 遞增的總數也是 O(n)，因此調整活動點的數目也就限制在了 O(n)。

代碼示例

下面代碼來自 GitHub 作者 Nathan Ridley。

  1 using System;
  2 using System.Collections.Generic;
  3 using System.IO;
  4 using System.Linq;
  5 using System.Text;
  6 
  7 namespace SuffixTreeAlgorithm
  8 {
  9   class Program
 10   {
 11     static void Main(string[] args)
 12     {
 13       var tree = new SuffixTree("abcabxabcd");
 14       tree.Message += (f, o) => { Console.WriteLine(f, o); };
 15       tree.Changed += (t) =>
 16       {
 17         Console.WriteLine(
 18           Environment.NewLine
 19           + t.RenderTree()
 20           + Environment.NewLine);
 21       };
 22       tree.Build('$');
 23 
 24       //SuffixTree.Create("abcabxabcd");
 25       //SuffixTree.Create("abcdefabxybcdmnabcdex");
 26       //SuffixTree.Create("abcadak");
 27       //SuffixTree.Create("dedododeeodo");
 28       //SuffixTree.Create("ooooooooo");
 29       //SuffixTree.Create("mississippi");
 30 
 31       Console.ReadKey();
 32     }
 33   }
 34 
 35   public class SuffixTree
 36   {
 37     public char? CanonizationChar { get; set; }
 38     public string Word { get; private set; }
 39     private int CurrentSuffixStartIndex { get; set; }
 40     private int CurrentSuffixEndIndex { get; set; }
 41     private Node LastCreatedNodeInCurrentIteration { get; set; }
 42     private int UnresolvedSuffixes { get; set; }
 43     public Node RootNode { get; private set; }
 44     private Node ActiveNode { get; set; }
 45     private Edge ActiveEdge { get; set; }
 46     private int DistanceIntoActiveEdge { get; set; }
 47     private char LastCharacterOfCurrentSuffix { get; set; }
 48     private int NextNodeNumber { get; set; }
 49     private int NextEdgeNumber { get; set; }
 50 
 51     public SuffixTree(string word)
 52     {
 53       Word = word;
 54       RootNode = new Node(this);
 55       ActiveNode = RootNode;
 56     }
 57 
 58     public event Action<SuffixTree> Changed;
 59     private void TriggerChanged()
 60     {
 61       var handler = Changed;
 62       if (handler != null)
 63         handler(this);
 64     }
 65 
 66     public event Action<string, object[]> Message;
 67     private void SendMessage(string format, params object[] args)
 68     {
 69       var handler = Message;
 70       if (handler != null)
 71         handler(format, args);
 72     }
 73 
 74     public static SuffixTree Create(string word, char canonizationChar = '$')
 75     {
 76       var tree = new SuffixTree(word);
 77       tree.Build(canonizationChar);
 78       return tree;
 79     }
 80 
 81     public void Build(char canonizationChar)
 82     {
 83       var n = Word.IndexOf(Word[Word.Length - 1]);
 84       var mustCanonize = n < Word.Length - 1;
 85       if (mustCanonize)
 86       {
 87         CanonizationChar = canonizationChar;
 88         Word = string.Concat(Word, canonizationChar);
 89       }
 90 
 91       for (CurrentSuffixEndIndex = 0; CurrentSuffixEndIndex < Word.Length; CurrentSuffixEndIndex++)
 92       {
 93         SendMessage("=== ITERATION {0} ===", CurrentSuffixEndIndex);
 94         LastCreatedNodeInCurrentIteration = null;
 95         LastCharacterOfCurrentSuffix = Word[CurrentSuffixEndIndex];
 96 
 97         for (CurrentSuffixStartIndex = CurrentSuffixEndIndex - UnresolvedSuffixes; CurrentSuffixStartIndex <= CurrentSuffixEndIndex; CurrentSuffixStartIndex++)
 98         {
 99           var wasImplicitlyAdded = !AddNextSuffix();
100           if (wasImplicitlyAdded)
101           {
102             UnresolvedSuffixes++;
103             break;
104           }
105           if (UnresolvedSuffixes > 0)
106             UnresolvedSuffixes--;
107         }
108       }
109     }
110 
111     private bool AddNextSuffix()
112     {
113       var suffix = string.Concat(Word.Substring(CurrentSuffixStartIndex, CurrentSuffixEndIndex - CurrentSuffixStartIndex), "{", Word[CurrentSuffixEndIndex], "}");
114       SendMessage("The next suffix of '{0}' to add is '{1}' at indices {2},{3}", Word, suffix, CurrentSuffixStartIndex, CurrentSuffixEndIndex);
115       SendMessage(" => ActiveNode:             {0}", ActiveNode);
116       SendMessage(" => ActiveEdge:             {0}", ActiveEdge == null ? "none" : ActiveEdge.ToString());
117       SendMessage(" => DistanceIntoActiveEdge: {0}", DistanceIntoActiveEdge);
118       SendMessage(" => UnresolvedSuffixes:     {0}", UnresolvedSuffixes);
119       if (ActiveEdge != null && DistanceIntoActiveEdge >= ActiveEdge.Length)
120         throw new Exception("BOUNDARY EXCEEDED");
121 
122       if (ActiveEdge != null)
123         return AddCurrentSuffixToActiveEdge();
124 
125       if (GetExistingEdgeAndSetAsActive())
126         return false;
127 
128       ActiveNode.AddNewEdge();
129       TriggerChanged();
130 
131       UpdateActivePointAfterAddingNewEdge();
132       return true;
133     }
134 
135     private bool GetExistingEdgeAndSetAsActive()
136     {
137       Edge edge;
138       if (ActiveNode.Edges.TryGetValue(LastCharacterOfCurrentSuffix, out edge))
139       {
140         SendMessage("Existing edge for {0} starting with '{1}' found. Values adjusted to:", ActiveNode, LastCharacterOfCurrentSuffix);
141         ActiveEdge = edge;
142         DistanceIntoActiveEdge = 1;
143         TriggerChanged();
144 
145         NormalizeActivePointIfNowAtOrBeyondEdgeBoundary(ActiveEdge.StartIndex);
146         SendMessage(" => ActiveEdge is now: {0}", ActiveEdge);
147         SendMessage(" => DistanceIntoActiveEdge is now: {0}", DistanceIntoActiveEdge);
148         SendMessage(" => UnresolvedSuffixes is now: {0}", UnresolvedSuffixes);
149 
150         return true;
151       }
152       SendMessage("Existing edge for {0} starting with '{1}' not found", ActiveNode, LastCharacterOfCurrentSuffix);
153       return false;
154     }
155 
156     private bool AddCurrentSuffixToActiveEdge()
157     {
158       var nextCharacterOnEdge = Word[ActiveEdge.StartIndex + DistanceIntoActiveEdge];
159       if (nextCharacterOnEdge == LastCharacterOfCurrentSuffix)
160       {
161         SendMessage("The next character on the current edge is '{0}' (suffix added implicitly)", LastCharacterOfCurrentSuffix);
162         DistanceIntoActiveEdge++;
163         TriggerChanged();
164 
165         SendMessage(" => DistanceIntoActiveEdge is now: {0}", DistanceIntoActiveEdge);
166         NormalizeActivePointIfNowAtOrBeyondEdgeBoundary(ActiveEdge.StartIndex);
167 
168         return false;
169       }
170 
171       SplitActiveEdge();
172       ActiveEdge.Tail.AddNewEdge();
173       TriggerChanged();
174 
175       UpdateActivePointAfterAddingNewEdge();
176 
177       return true;
178     }
179 
180     private void UpdateActivePointAfterAddingNewEdge()
181     {
182       if (ReferenceEquals(ActiveNode, RootNode))
183       {
184         if (DistanceIntoActiveEdge > 0)
185         {
186           SendMessage("New edge has been added and the active node is root. The active edge will now be updated.");
187           DistanceIntoActiveEdge--;
188           SendMessage(" => DistanceIntoActiveEdge decremented to: {0}", DistanceIntoActiveEdge);
189           ActiveEdge = DistanceIntoActiveEdge == 0 ? null : ActiveNode.Edges[Word[CurrentSuffixStartIndex + 1]];
190           SendMessage(" => ActiveEdge is now: {0}", ActiveEdge);
191           TriggerChanged();
192 
193           NormalizeActivePointIfNowAtOrBeyondEdgeBoundary(CurrentSuffixStartIndex + 1);
194         }
195       }
196       else
197         UpdateActivePointToLinkedNodeOrRoot();
198     }
199 
200     private void NormalizeActivePointIfNowAtOrBeyondEdgeBoundary(int firstIndexOfOriginalActiveEdge)
201     {
202       var walkDistance = 0;
203       while (ActiveEdge != null && DistanceIntoActiveEdge >= ActiveEdge.Length)
204       {
205         SendMessage("Active point is at or beyond edge boundary and will be moved until it falls inside an edge boundary");
206         DistanceIntoActiveEdge -= ActiveEdge.Length;
207         ActiveNode = ActiveEdge.Tail ?? RootNode;
208         if (DistanceIntoActiveEdge == 0)
209           ActiveEdge = null;
210         else
211         {
212           walkDistance += ActiveEdge.Length;
213           var c = Word[firstIndexOfOriginalActiveEdge + walkDistance];
214           ActiveEdge = ActiveNode.Edges[c];
215         }
216         TriggerChanged();
217       }
218     }
219 
220     private void SplitActiveEdge()
221     {
222       ActiveEdge = ActiveEdge.SplitAtIndex(ActiveEdge.StartIndex + DistanceIntoActiveEdge);
223       SendMessage(" => ActiveEdge is now: {0}", ActiveEdge);
224       TriggerChanged();
225       if (LastCreatedNodeInCurrentIteration != null)
226       {
227         LastCreatedNodeInCurrentIteration.LinkedNode = ActiveEdge.Tail;
228         SendMessage(" => Connected {0} to {1}", LastCreatedNodeInCurrentIteration, ActiveEdge.Tail);
229         TriggerChanged();
230       }
231       LastCreatedNodeInCurrentIteration = ActiveEdge.Tail;
232     }
233 
234     private void UpdateActivePointToLinkedNodeOrRoot()
235     {
236       SendMessage("The linked node for active node {0} is {1}", ActiveNode, ActiveNode.LinkedNode == null ? "[null]" : ActiveNode.LinkedNode.ToString());
237       if (ActiveNode.LinkedNode != null)
238       {
239         ActiveNode = ActiveNode.LinkedNode;
240         SendMessage(" => ActiveNode is now: {0}", ActiveNode);
241       }
242       else
243       {
244         ActiveNode = RootNode;
245         SendMessage(" => ActiveNode is now ROOT", ActiveNode);
246       }
247       TriggerChanged();
248 
249       if (ActiveEdge != null)
250       {
251         var firstIndexOfOriginalActiveEdge = ActiveEdge.StartIndex;
252         ActiveEdge = ActiveNode.Edges[Word[ActiveEdge.StartIndex]];
253         TriggerChanged();
254         NormalizeActivePointIfNowAtOrBeyondEdgeBoundary(firstIndexOfOriginalActiveEdge);
255       }
256     }
257 
258     public string RenderTree()
259     {
260       var writer = new StringWriter();
261       RootNode.RenderTree(writer, "");
262       return writer.ToString();
263     }
264 
265     public string WriteDotGraph()
266     {
267       var sb = new StringBuilder();
268       sb.AppendLine("digraph {");
269       sb.AppendLine("rankdir = LR;");
270       sb.AppendLine("edge [arrowsize=0.5,fontsize=11];");
271       for (var i = 0; i < NextNodeNumber; i++)
272         sb.AppendFormat("node{0} [label=\"{0}\",style=filled,fillcolor={1},shape=circle,width=.1,height=.1,fontsize=11,margin=0.01];",
273           i, ActiveNode.NodeNumber == i ? "cyan" : "lightgrey").AppendLine();
274       RootNode.WriteDotGraph(sb);
275       sb.AppendLine("}");
276       return sb.ToString();
277     }
278 
279     public HashSet<string> ExtractAllSubstrings()
280     {
281       var set = new HashSet<string>();
282       ExtractAllSubstrings("", set, RootNode);
283       return set;
284     }
285 
286     private void ExtractAllSubstrings(string str, HashSet<string> set, Node node)
287     {
288       foreach (var edge in node.Edges.Values)
289       {
290         var edgeStr = edge.StringWithoutCanonizationChar;
291         var edgeLength = !edge.EndIndex.HasValue && CanonizationChar.HasValue ? edge.Length - 1 : edge.Length; // assume tailing canonization char
292         for (var length = 1; length <= edgeLength; length++)
293           set.Add(string.Concat(str, edgeStr.Substring(0, length)));
294         if (edge.Tail != null)
295           ExtractAllSubstrings(string.Concat(str, edge.StringWithoutCanonizationChar), set, edge.Tail);
296       }
297     }
298 
299     public List<string> ExtractSubstringsForIndexing(int? maxLength = null)
300     {
301       var list = new List<string>();
302       ExtractSubstringsForIndexing("", list, maxLength ?? Word.Length, RootNode);
303       return list;
304     }
305 
306     private void ExtractSubstringsForIndexing(string str, List<string> list, int len, Node node)
307     {
308       foreach (var edge in node.Edges.Values)
309       {
310         var newstr = string.Concat(str, Word.Substring(edge.StartIndex, Math.Min(len, edge.Length)));
311         if (len > edge.Length && edge.Tail != null)
312           ExtractSubstringsForIndexing(newstr, list, len - edge.Length, edge.Tail);
313         else
314           list.Add(newstr);
315       }
316     }
317 
318     public class Edge
319     {
320       private readonly SuffixTree _tree;
321 
322       public Edge(SuffixTree tree, Node head)
323       {
324         _tree = tree;
325         Head = head;
326         StartIndex = tree.CurrentSuffixEndIndex;
327         EdgeNumber = _tree.NextEdgeNumber++;
328       }
329 
330       public Node Head { get; private set; }
331       public Node Tail { get; private set; }
332       public int StartIndex { get; private set; }
333       public int? EndIndex { get; set; }
334       public int EdgeNumber { get; private set; }
335       public int Length { get { return (EndIndex ?? _tree.Word.Length - 1) - StartIndex + 1; } }
336 
337       public Edge SplitAtIndex(int index)
338       {
339         _tree.SendMessage("Splitting edge {0} at index {1} ('{2}')", this, index, _tree.Word[index]);
340         var newEdge = new Edge(_tree, Head);
341         var newNode = new Node(_tree);
342         newEdge.Tail = newNode;
343         newEdge.StartIndex = StartIndex;
344         newEdge.EndIndex = index - 1;
345         Head = newNode;
346         StartIndex = index;
347         newNode.Edges.Add(_tree.Word[StartIndex], this);
348         newEdge.Head.Edges[_tree.Word[newEdge.StartIndex]] = newEdge;
349         _tree.SendMessage(" => Hierarchy is now: {0} --> {1} --> {2} --> {3}", newEdge.Head, newEdge, newNode, this);
350         return newEdge;
351       }
352 
353       public override string ToString()
354       {
355         return string.Concat(_tree.Word.Substring(StartIndex, (EndIndex ?? _tree.CurrentSuffixEndIndex) - StartIndex + 1), "(",
356           StartIndex, ",", EndIndex.HasValue ? EndIndex.ToString() : "#", ")");
357       }
358 
359       public string StringWithoutCanonizationChar
360       {
361         get { return _tree.Word.Substring(StartIndex, (EndIndex ?? _tree.CurrentSuffixEndIndex - (_tree.CanonizationChar.HasValue ? 1 : 0)) - StartIndex + 1); }
362       }
363 
364       public string String
365       {
366         get { return _tree.Word.Substring(StartIndex, (EndIndex ?? _tree.CurrentSuffixEndIndex) - StartIndex + 1); }
367       }
368 
369       public void RenderTree(TextWriter writer, string prefix, int maxEdgeLength)
370       {
371         var strEdge = _tree.Word.Substring(StartIndex, (EndIndex ?? _tree.CurrentSuffixEndIndex) - StartIndex + 1);
372         writer.Write(strEdge);
373         if (Tail == null)
374           writer.WriteLine();
375         else
376         {
377           var line = new string(RenderChars.HorizontalLine, maxEdgeLength - strEdge.Length + 1);
378           writer.Write(line);
379           Tail.RenderTree(writer, string.Concat(prefix, new string(' ', strEdge.Length + line.Length)));
380         }
381       }
382 
383       public void WriteDotGraph(StringBuilder sb)
384       {
385         if (Tail == null)
386           sb.AppendFormat("leaf{0} [label=\"\",shape=point]", EdgeNumber).AppendLine();
387         string label, weight, color;
388         if (_tree.ActiveEdge != null && ReferenceEquals(this, _tree.ActiveEdge))
389         {
390           if (_tree.ActiveEdge.Length == 0)
391             label = "";
392           else if (_tree.DistanceIntoActiveEdge > Length)
393             label = "<<FONT COLOR=\"red\" SIZE=\"11\"><B>" + String + "</B> (" + _tree.DistanceIntoActiveEdge + ")</FONT>>";
394           else if (_tree.DistanceIntoActiveEdge == Length)
395             label = "<<FONT COLOR=\"red\" SIZE=\"11\">" + String + "</FONT>>";
396           else if (_tree.DistanceIntoActiveEdge > 0)
397             label = "<<TABLE BORDER=\"0\" CELLPADDING=\"0\" CELLSPACING=\"0\"><TR><TD><FONT COLOR=\"blue\"><B>" + String.Substring(0, _tree.DistanceIntoActiveEdge) + "</B></FONT></TD><TD COLOR=\"black\">" + String.Substring(_tree.DistanceIntoActiveEdge) + "</TD></TR></TABLE>>";
398           else
399             label = "\"" + String + "\"";
400           color = "blue";
401           weight = "5";
402         }
403         else
404         {
405           label = "\"" + String + "\"";
406           color = "black";
407           weight = "3";
408         }
409         var tail = Tail == null ? "leaf" + EdgeNumber : "node" + Tail.NodeNumber;
410         sb.AppendFormat("node{0} -> {1} [label={2},weight={3},color={4},size=11]", Head.NodeNumber, tail, label, weight, color).AppendLine();
411         if (Tail != null)
412           Tail.WriteDotGraph(sb);
413       }
414     }
415 
416     public class Node
417     {
418       private readonly SuffixTree _tree;
419 
420       public Node(SuffixTree tree)
421       {
422         _tree = tree;
423         Edges = new Dictionary<char, Edge>();
424         NodeNumber = _tree.NextNodeNumber++;
425       }
426 
427       public Dictionary<char, Edge> Edges { get; private set; }
428       public Node LinkedNode { get; set; }
429       public int NodeNumber { get; private set; }
430 
431       public void AddNewEdge()
432       {
433         _tree.SendMessage("Adding new edge to {0}", this);
434         var edge = new Edge(_tree, this);
435         Edges.Add(_tree.Word[_tree.CurrentSuffixEndIndex], edge);
436         _tree.SendMessage(" => {0} --> {1}", this, edge);
437       }
438 
439       public void RenderTree(TextWriter writer, string prefix)
440       {
441         var strNode = string.Concat("(", NodeNumber.ToString(new string('0', _tree.NextNodeNumber.ToString().Length)), ")");
442         writer.Write(strNode);
443         var edges = Edges.Select(kvp => kvp.Value).OrderBy(e => _tree.Word[e.StartIndex]).ToArray();
444         if (edges.Any())
445         {
446           var prefixWithNodePadding = prefix + new string(' ', strNode.Length);
447           var maxEdgeLength = edges.Max(e => (e.EndIndex ?? _tree.CurrentSuffixEndIndex) - e.StartIndex + 1);
448           for (var i = 0; i < edges.Length; i++)
449           {
450             char connector, extender = ' ';
451             if (i == 0)
452             {
453               if (edges.Length > 1)
454               {
455                 connector = RenderChars.TJunctionDown;
456                 extender = RenderChars.VerticalLine;
457               }
458               else
459                 connector = RenderChars.HorizontalLine;
460             }
461             else
462             {
463               writer.Write(prefixWithNodePadding);
464               if (i == edges.Length - 1)
465                 connector = RenderChars.CornerRight;
466               else
467               {
468                 connector = RenderChars.TJunctionRight;
469                 extender = RenderChars.VerticalLine;
470               }
471             }
472             writer.Write(string.Concat(connector, RenderChars.HorizontalLine));
473             var newPrefix = string.Concat(prefixWithNodePadding, extender, ' ');
474             edges[i].RenderTree(writer, newPrefix, maxEdgeLength);
475           }
476         }
477       }
478 
479       public override string ToString()
480       {
481         return string.Concat("node #", NodeNumber);
482       }
483 
484       public void WriteDotGraph(StringBuilder sb)
485       {
486         if (LinkedNode != null)
487           sb.AppendFormat("node{0} -> node{1} [label=\"\",weight=.01,style=dotted]", NodeNumber, LinkedNode.NodeNumber).AppendLine();
488         foreach (var edge in Edges.Values)
489           edge.WriteDotGraph(sb);
490       }
491     }
492 
493     public static class RenderChars
494     {
495       public const char TJunctionDown = '┬';
496       public const char HorizontalLine = '─';
497       public const char VerticalLine = '│';
498       public const char TJunctionRight = '├';
499       public const char CornerRight = '└';
500     }
501   }
502 }

運行結果

測試 Text = "abcabxabcd"。

=== ITERATION 0 ===
The next suffix of 'abcabxabcd' to add is '{a}' at indices 0,0
 => ActiveNode:             node #0
 => ActiveEdge:             none
 => DistanceIntoActiveEdge: 0
 => UnresolvedSuffixes:     0
Existing edge for node #0 starting with 'a' not found
Adding new edge to node #0
 => node #0 --> a(0,#)

(0)──a


=== ITERATION 1 ===
The next suffix of 'abcabxabcd' to add is '{b}' at indices 1,1
 => ActiveNode:             node #0
 => ActiveEdge:             none
 => DistanceIntoActiveEdge: 0
 => UnresolvedSuffixes:     0
Existing edge for node #0 starting with 'b' not found
Adding new edge to node #0
 => node #0 --> b(1,#)

(0)┬─ab
   └─b


=== ITERATION 2 ===
The next suffix of 'abcabxabcd' to add is '{c}' at indices 2,2
 => ActiveNode:             node #0
 => ActiveEdge:             none
 => DistanceIntoActiveEdge: 0
 => UnresolvedSuffixes:     0
Existing edge for node #0 starting with 'c' not found
Adding new edge to node #0
 => node #0 --> c(2,#)

(0)┬─abc
   ├─bc
   └─c


=== ITERATION 3 ===
The next suffix of 'abcabxabcd' to add is '{a}' at indices 3,3
 => ActiveNode:             node #0
 => ActiveEdge:             none
 => DistanceIntoActiveEdge: 0
 => UnresolvedSuffixes:     0
Existing edge for node #0 starting with 'a' found. Values adjusted to:

(0)┬─abca
   ├─bca
   └─ca


 => ActiveEdge is now: abca(0,#)
 => DistanceIntoActiveEdge is now: 1
 => UnresolvedSuffixes is now: 0
=== ITERATION 4 ===
The next suffix of 'abcabxabcd' to add is 'a{b}' at indices 3,4
 => ActiveNode:             node #0
 => ActiveEdge:             abcab(0,#)
 => DistanceIntoActiveEdge: 1
 => UnresolvedSuffixes:     1
The next character on the current edge is 'b' (suffix added implicitly)

(0)┬─abcab
   ├─bcab
   └─cab


 => DistanceIntoActiveEdge is now: 2
=== ITERATION 5 ===
The next suffix of 'abcabxabcd' to add is 'ab{x}' at indices 3,5
 => ActiveNode:             node #0
 => ActiveEdge:             abcabx(0,#)
 => DistanceIntoActiveEdge: 2
 => UnresolvedSuffixes:     2
Splitting edge abcabx(0,#) at index 2 ('c')
 => Hierarchy is now: node #0 --> ab(0,1) --> node #1 --> cabx(2,#)
 => ActiveEdge is now: ab(0,1)

(0)┬─ab────(1)──cabx
   ├─bcabx
   └─cabx


Adding new edge to node #1
 => node #1 --> x(5,#)

(0)┬─ab────(1)┬─cabx
   │          └─x
   ├─bcabx
   └─cabx


New edge has been added and the active node is root. The active edge will now be
 updated.
 => DistanceIntoActiveEdge decremented to: 1
 => ActiveEdge is now: bcabx(1,#)

(0)┬─ab────(1)┬─cabx
   │          └─x
   ├─bcabx
   └─cabx


The next suffix of 'abcabxabcd' to add is 'b{x}' at indices 4,5
 => ActiveNode:             node #0
 => ActiveEdge:             bcabx(1,#)
 => DistanceIntoActiveEdge: 1
 => UnresolvedSuffixes:     1
Splitting edge bcabx(1,#) at index 2 ('c')
 => Hierarchy is now: node #0 --> b(1,1) --> node #2 --> cabx(2,#)
 => ActiveEdge is now: b(1,1)

(0)┬─ab───(1)┬─cabx
   │         └─x
   ├─b────(2)──cabx
   └─cabx


 => Connected node #1 to node #2

(0)┬─ab───(1)┬─cabx
   │         └─x
   ├─b────(2)──cabx
   └─cabx


Adding new edge to node #2
 => node #2 --> x(5,#)

(0)┬─ab───(1)┬─cabx
   │         └─x
   ├─b────(2)┬─cabx
   │         └─x
   └─cabx


New edge has been added and the active node is root. The active edge will now be
 updated.
 => DistanceIntoActiveEdge decremented to: 0
 => ActiveEdge is now:

(0)┬─ab───(1)┬─cabx
   │         └─x
   ├─b────(2)┬─cabx
   │         └─x
   └─cabx


The next suffix of 'abcabxabcd' to add is '{x}' at indices 5,5
 => ActiveNode:             node #0
 => ActiveEdge:             none
 => DistanceIntoActiveEdge: 0
 => UnresolvedSuffixes:     0
Existing edge for node #0 starting with 'x' not found
Adding new edge to node #0
 => node #0 --> x(5,#)

(0)┬─ab───(1)┬─cabx
   │         └─x
   ├─b────(2)┬─cabx
   │         └─x
   ├─cabx
   └─x


=== ITERATION 6 ===
The next suffix of 'abcabxabcd' to add is '{a}' at indices 6,6
 => ActiveNode:             node #0
 => ActiveEdge:             none
 => DistanceIntoActiveEdge: 0
 => UnresolvedSuffixes:     0
Existing edge for node #0 starting with 'a' found. Values adjusted to:

(0)┬─ab────(1)┬─cabxa
   │          └─xa
   ├─b─────(2)┬─cabxa
   │          └─xa
   ├─cabxa
   └─xa


 => ActiveEdge is now: ab(0,1)
 => DistanceIntoActiveEdge is now: 1
 => UnresolvedSuffixes is now: 0
=== ITERATION 7 ===
The next suffix of 'abcabxabcd' to add is 'a{b}' at indices 6,7
 => ActiveNode:             node #0
 => ActiveEdge:             ab(0,1)
 => DistanceIntoActiveEdge: 1
 => UnresolvedSuffixes:     1
The next character on the current edge is 'b' (suffix added implicitly)

(0)┬─ab─────(1)┬─cabxab
   │           └─xab
   ├─b──────(2)┬─cabxab
   │           └─xab
   ├─cabxab
   └─xab


 => DistanceIntoActiveEdge is now: 2
Active point is at or beyond edge boundary and will be moved until it falls insi
de an edge boundary

(0)┬─ab─────(1)┬─cabxab
   │           └─xab
   ├─b──────(2)┬─cabxab
   │           └─xab
   ├─cabxab
   └─xab


=== ITERATION 8 ===
The next suffix of 'abcabxabcd' to add is 'ab{c}' at indices 6,8
 => ActiveNode:             node #1
 => ActiveEdge:             none
 => DistanceIntoActiveEdge: 0
 => UnresolvedSuffixes:     2
Existing edge for node #1 starting with 'c' found. Values adjusted to:

(0)┬─ab──────(1)┬─cabxabc
   │            └─xabc
   ├─b───────(2)┬─cabxabc
   │            └─xabc
   ├─cabxabc
   └─xabc


 => ActiveEdge is now: cabxabc(2,#)
 => DistanceIntoActiveEdge is now: 1
 => UnresolvedSuffixes is now: 2
=== ITERATION 9 ===
The next suffix of 'abcabxabcd' to add is 'abc{d}' at indices 6,9
 => ActiveNode:             node #1
 => ActiveEdge:             cabxabcd(2,#)
 => DistanceIntoActiveEdge: 1
 => UnresolvedSuffixes:     3
Splitting edge cabxabcd(2,#) at index 3 ('a')
 => Hierarchy is now: node #1 --> c(2,2) --> node #3 --> abxabcd(3,#)
 => ActiveEdge is now: c(2,2)

(0)┬─ab───────(1)┬─c─────(3)──abxabcd
   │             └─xabcd
   ├─b────────(2)┬─cabxabcd
   │             └─xabcd
   ├─cabxabcd
   └─xabcd


Adding new edge to node #3
 => node #3 --> d(9,#)

(0)┬─ab───────(1)┬─c─────(3)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─b────────(2)┬─cabxabcd
   │             └─xabcd
   ├─cabxabcd
   └─xabcd


The linked node for active node node #1 is node #2
 => ActiveNode is now: node #2

(0)┬─ab───────(1)┬─c─────(3)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─b────────(2)┬─cabxabcd
   │             └─xabcd
   ├─cabxabcd
   └─xabcd



(0)┬─ab───────(1)┬─c─────(3)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─b────────(2)┬─cabxabcd
   │             └─xabcd
   ├─cabxabcd
   └─xabcd


The next suffix of 'abcabxabcd' to add is 'bc{d}' at indices 7,9
 => ActiveNode:             node #2
 => ActiveEdge:             cabxabcd(2,#)
 => DistanceIntoActiveEdge: 1
 => UnresolvedSuffixes:     2
Splitting edge cabxabcd(2,#) at index 3 ('a')
 => Hierarchy is now: node #2 --> c(2,2) --> node #4 --> abxabcd(3,#)
 => ActiveEdge is now: c(2,2)

(0)┬─ab───────(1)┬─c─────(3)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─b────────(2)┬─c─────(4)──abxabcd
   │             └─xabcd
   ├─cabxabcd
   └─xabcd


 => Connected node #3 to node #4

(0)┬─ab───────(1)┬─c─────(3)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─b────────(2)┬─c─────(4)──abxabcd
   │             └─xabcd
   ├─cabxabcd
   └─xabcd


Adding new edge to node #4
 => node #4 --> d(9,#)

(0)┬─ab───────(1)┬─c─────(3)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─b────────(2)┬─c─────(4)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─cabxabcd
   └─xabcd


The linked node for active node node #2 is [null]
 => ActiveNode is now ROOT

(0)┬─ab───────(1)┬─c─────(3)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─b────────(2)┬─c─────(4)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─cabxabcd
   └─xabcd



(0)┬─ab───────(1)┬─c─────(3)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─b────────(2)┬─c─────(4)┬─abxabcd
   │             │          └─d
   │             └─xabcd
   ├─cabxabcd
   └─xabcd


The next suffix of 'abcabxabcd' to add is 'c{d}' at indices 8,9
 => ActiveNode:             node #0
 => ActiveEdge:             cabxabcd(2,#)
 => DistanceIntoActiveEdge: 1
 => UnresolvedSuffixes:     1
Splitting edge cabxabcd(2,#) at index 3 ('a')
 => Hierarchy is now: node #0 --> c(2,2) --> node #5 --> abxabcd(3,#)
 => ActiveEdge is now: c(2,2)

(0)┬─ab────(1)┬─c─────(3)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─b─────(2)┬─c─────(4)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─c─────(5)──abxabcd
   └─xabcd


 => Connected node #4 to node #5

(0)┬─ab────(1)┬─c─────(3)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─b─────(2)┬─c─────(4)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─c─────(5)──abxabcd
   └─xabcd


Adding new edge to node #5
 => node #5 --> d(9,#)

(0)┬─ab────(1)┬─c─────(3)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─b─────(2)┬─c─────(4)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─c─────(5)┬─abxabcd
   │          └─d
   └─xabcd


New edge has been added and the active node is root. The active edge will now be
 updated.
 => DistanceIntoActiveEdge decremented to: 0
 => ActiveEdge is now:

(0)┬─ab────(1)┬─c─────(3)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─b─────(2)┬─c─────(4)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─c─────(5)┬─abxabcd
   │          └─d
   └─xabcd


The next suffix of 'abcabxabcd' to add is '{d}' at indices 9,9
 => ActiveNode:             node #0
 => ActiveEdge:             none
 => DistanceIntoActiveEdge: 0
 => UnresolvedSuffixes:     0
Existing edge for node #0 starting with 'd' not found
Adding new edge to node #0
 => node #0 --> d(9,#)

(0)┬─ab────(1)┬─c─────(3)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─b─────(2)┬─c─────(4)┬─abxabcd
   │          │          └─d
   │          └─xabcd
   ├─c─────(5)┬─abxabcd
   │          └─d
   ├─d
   └─xabcd

后綴樹的應用

查找字符串 Pattern 是否在于字符串 Text 中
- 方案：用 Text 構造后綴樹，按在 Trie 中搜索字串的方法搜索 Pattern 即可。若 Pattern 在 Text 中，則 Pattern 必然是 Text 的某個后綴的前綴。
計算指定字符串 Pattern 在字符串 Text 中的出現次數
- 方案：用 Text+'$' 構造后綴樹，搜索 Pattern 所在節點下的葉節點數目即為重復次數。如果 Pattern 在 Text 中重復了 c 次，則 Text 應有 c 個后綴以 Pattern 為前綴。
查找字符串 Text 中的最長重復子串
- 方案：用 Text+'$' 構造后綴樹，搜索 Pattern 所在節點下的最深的非葉節點。從 root 到該節點所經歷過的字符串就是最長重復子串。
查找兩個字符串 Text1 和 Text2 的最長公共部分
- 方案：連接 Text1+'#' + Text2+'$' 形成新的字符串并構造后綴樹，找到最深的非葉節點，且該節點的葉節點既有 '#' 也有 '$'。
查找給定字符串 Text 里的最長回文
- 回文指："abcdefgfed" 中對稱的字符串 "defgfed"。
- 回文半徑指：回文 "defgfed" 的回文半徑 "defg" 長度為 4，半徑中心為字母 "g"。
- 方案：將 Text 整體反轉形成新的字符串 Text2，例如 "abcdefgfed" => "defgfedcba"。連接 Text+'#' + Text2+'$' 形成新的字符串并構造后綴樹，然后將問題轉變為查找 Text 和 Text1 的最長公共部分。