字尾樹與字尾數組

http://imlazy.ycool.com/post.2011818.html 

字尾樹和字尾數組簡直就是 ACM

選手必備的知識啊，我已經在兩次比賽中碰到過相關的問題了。我甚至還寫過一篇應用的文章，可是我真是井底之蛙啊，

那時我還不知道這個叫字尾數組，還有更好的構造算法，還有很多的應用。最近終于好好在這方面掃了個盲，在此小小地總結一下。

    假設有一個長度為 n 的字元串 T[0 ... n)；S(i) 表示 T 的從下标 i 開始的字尾，即 T[i ... n)。那麼 T 的後

綴數組就是把 S(i) ~ S(n - 1) 這 n 個字尾按字典序排好序的一個數組。它對于

查找 T 的子串之類的問題是很有用的。問題就在于怎樣快速地把這些字尾排好序。

    最簡單的方法就是把所有 S(i) 快速排序。快速排序本身的時間是 O(n log

n)，但是由于排序的對象是一個個字元串，是以每次比較的時間在最差情況下都會變成線性的（也就是 O(n) 的），是以總的時間在最差情況下可能會升到

O(n2) 左右，這就很慢了。對此，我學到了三個更快的算法。

1. Ukkonen 算法

    Ukkonen 算法先用 O(n) 的時間構造一棵字尾樹，然後再用 O(n)

的時間從字尾樹得到字尾數組。在這個網址，介紹了作者 Esko Ukkonen，并列出了他的一些論文；其中的一篇《On-line construction of suffix-trees》是可以下載下傳的，裡面就講解了什麼

是字尾樹，怎樣在 O(n) 的時間内構造它，以及怎樣從它得到字尾數組。

    不過我一開始還沒發現這篇論文，我是從 Dan Gusfield 的《Algorithms on Strings, Trees and

Sequences - COMPUTER SCIENCE AND COMPUTATIONAL

BIOLOGY》這本書裡學到這個算法的。這本書在中國沒的賣，想買的話，可以找代購網站去 Amazon 買。我是在 eMule

上搜到并下載下傳的。這本書中的這節内容講得還可以，雖然我覺得它示例比較少，但是花了點功夫還是看懂了。學會了之後，原作者的論文我就沒有仔細看過了，是以

沒法評論。

   Ukkonen

算法還是比較複雜的，代碼比較長；而且字尾樹這個結構本身也比較費空間。總而言之，雖然該算法在理論上是最快的，字尾樹也是一個很優美的結構，但是在許多

實際應用中不是很實惠。

    然而，一開始我還不知道别的算法時，還是把它實作了出來（代碼 1、代碼 2）。（我

寫了兩個版本，它們的不同點在于每個節點的子節點的存放方式。代碼 1 是用數組，代碼 2 是用連結清單。用數組的話，查找指定的子節點很快，隻要

O(1)；但是比較費空間。用連結清單的話，省空間，但是查找子節點比較慢，隻能線性地查找，不過一般情況下問題不大。實際上，我在 PKU

3415 這道題中，用數組反而比用連結清單慢，可能前者配置設定空間所花的時間比較多吧。）

2. DC3 算法

   我在 Google 上搜到了這篇論文，《Linear Work Suffix Array Construction》，其中介紹了一個可以在

O(3n) 的時間内構造出字尾數組的算法，叫作 DC3 (Difference Cover mod 3) 算法。

    該算法的基本原理大緻是這樣的。針對所有字尾的前 3 個字元，做基數排序；對于不滿 3 個字元的字尾，排序時在後面補 0（這裡的 0

是結束符，在 T 中不能出現；0 的字典序最優先）；排序時還要包括進從結束符（即 T[n]）開始的字尾 S(n): “000”。如果所有字尾的前

3 個字元都不完全相同，那麼這一次就排好了，最後去掉多餘的 “000” 字尾（它一定排在第一個），就得到答案了，時間是 O(3n)。如果存在前

3 個字元相同的，則需要生成一個名次數組 R， R(i) 表示 S(i) 在排好序後位于第幾名（名次從 1 開始計），接着再用上述方法遞歸地求

R[0 ... n] 的字尾數組，其結果和 T 的字尾數組是完全對應的，也就是說 SR(i) 排在第幾位，則 S(i)

也應該排在第幾位。但問題是如果這樣遞歸層數多了，時間也就大大增加了。

    接下來，在上述算法的基礎上，需要一個優化。首先，隻對滿足 i mod 3 = 1 或 i mod 3 = 2 的那些 S(i) 按照前 3

個字元進行基數排序；如果這其中有前 3 個字元相同的，同樣也需要遞歸地求它們的名次數組的字尾數組。排好了 i mod 3 = 1、2

的字尾之後，就可以得到一個總的名次數組 R，其中那些 i mod 3 = 0 的字尾的名次還是未知的。接着對于所有 i mod 3 = 0 的

S(i)，靠 T[i] 和 R(i + 1) 這兩個關鍵字就可以對它們排序了。最後把排好序的 mod 3 = 1、2 和 mod 3 = 0

的字尾歸并起來就是答案了。歸并的時候，比較兩個字尾 S(i) 和 S(j) 的方法也是看它們的前 3 個字元，如果都相同，那麼比較 R(i +

1) 和 R(j + 1)，若不可比（其中有一個是未知的）則再比較 R(i + 2) 和 R(j + 2)。

    有了以上的優化，即使當中出現了需要遞歸的情況，每次遞歸求解的字元串長度也隻有原來的 2 /

3，那麼即使遞歸的層數再多，總的時間之和也是會收斂的。

    以上我隻是潦草地介紹一下，具體的還是自己看論文吧。論文寫得還是蠻清楚的。尤其是最後有一個用 C++

實作的代碼，其中有很多細節實作地很巧妙，很值得學習。

3. 倍增算法

    我是從 IOI 2004 國家集訓隊論文集中的一篇名為《字尾數組》的文章中學到這個算法的。該文章在 Google 上搜得到，講得還是蠻清楚的。我在此就不多介紹了，請自己看文章。

    倍增算法最大的優點是實作簡單，速度也還可以，O(n log n)。如果程式的時間要求不是很緊的話，應該作為首選的算法。這裡是

我對倍增算法的實作。

4. 多個字元串的字尾數組

在很多問題中，都需要求多個字元串的字尾數組，也就是把多個字元串的所有字尾都放在一起排序。這個結構對于查找公共子串之類的問題是很有用的。字尾樹是可

以表示多個字元串的，但是 DC3 算法和倍增算法都隻能求單個字元串的字尾數組。

    其實多個字元串的字尾數組可以轉化成單個字元串的字尾數組。比如要求 “abc” 和 “def” 這兩個字元串的字尾數組，可以轉化成求

“abc1def” 的字尾數組。其中 1 是字典順僅次于結束符 0 的字元，它也不出現在任何字元串中。這樣求出來的字尾數組和 “abc” 與

“def” 的字尾數組是等價的；隻是多了一個以 1 開頭的字尾，但它一定排序在最前面，很容易去掉。在倍增算法中，用 0 替代 1 好像也可以；在

DC3 算法中好像不能用 0 替代 1，但是我忘記怎麼重制那個錯誤了，是以現在也不好說。但是用 1 肯定是沒錯的，這樣符合

“結束符在字元串中不出現” 的原則。

    這篇文章我寫得比較潦草，因為我引用的幾篇文章本身都寫得很清楚了，我确實沒有什麼新發現。是以到此為止吧。