資料結構之字尾數組suffix array

 在字元串處理當中，字尾樹和字尾數組都是非常有力的工具，其中字尾樹大家了解得比較多，關于字尾數組則很少見于國内的資料。其實字尾是字尾樹的一個非常精巧的替代品，它比字尾樹容易程式設計實作，能夠實作字尾樹的很多功能而時間複雜度也不太遜色，并且，它比字尾樹所占用的空間小很多。可以說，在資訊學競賽中字尾數組比字尾樹要更為實用。是以在本文中筆者想介紹一下字尾數組的基本概念、構造方法，以及配合字尾數組的最長公共字首數組的構造方法，最後結合一些例子談談字尾數組的應用。

基本定義：

子串

 字元串 S 的子串 r[i..j] ， i ≤ j ，表示 r 串中從 i 到 j 這一段，就是順次排列 r[i],r[i+1],...,r[j] 形成的字元串。

字尾

   字尾是指從某個位置 i 開始到整個串末尾結束的一個特殊子串。字元串 r 的從 第 i 個字元開始的字尾表示為 Suffix(i) ，也就是Suffix(i)=r[i..len(r)] 。

大小比較

大小比較：關于字元串的大小比較，是指通常所說的“字典順序”比較，也就是對于兩個字元串u、v，令i 從1 開始順次比較u[i]和v[i]，如果u[i]=v[i]則令 i 加1，否則若u[i]<v[i]則認為u<v，u[i]>v[i]則認為u>v（也就是v<u），比較結束。如果i>len(u)或者i>len(v)仍比較不出結果，那麼若len(u)<len(v) 則認為u<v ，若len(u)=len(v) 則認為u=v ，若len(u)>len(v)則u>v。

從字元串的大小比較的定義來看，S 的兩個開頭位置不同的字尾u 和v 進行比較的結果不可能是相等，因為u=v 的必要條件len(u)=len(v)在這裡不可能滿足。

字尾數組：字尾數組SA 是一個一維數組，它儲存1..n 的某個排列SA[1]，SA[2]，……，SA[n]，并且保證Suffix(SA[i]) < Suffix(SA[i+1])，1≤i<n。也就是将S 的n 個字尾從小到大進行排序之後把排好序的字尾的開頭位置順次放入SA 中。

名次數組：名次數組Rank[i]儲存的是Suffix(i)在所有字尾中從小到大排列的“名次”。簡單的說，字尾數組是“排第幾的是誰？”，名次數組是“你排第幾？”。容易看出，字尾數組和名次數組為互逆運算。如圖1 所示。