字尾數組--處理字元串的利器

字尾數組是處理字元串的有力工具。字尾數組是字尾樹的一個非常精巧的替代品，它比字尾樹容易程式設計實作，能夠實作字尾樹的很多功能而時間複雜度也并不遜色，而且它比字尾樹所占用的記憶體空間小很多。

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

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

大小比較：關于字元串的大小比較，是指通常所說的“字典順序”比較，也就是對于兩個字元串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中。

1 字尾數組求最長公共子串（LCS）

解法：将兩個字元串用一個特殊符号（兩個字元串中都沒有，比如‘#’）連接配接起來，構造連接配接後字元串的字尾數組，求字尾數組中的最長公共字首，要保證最長的公共字首在原來兩個字元串中都出現，而不是隻出現在一個字元串中，這就是特殊連接配接符号的作用。

2 字尾數組求最長回文子串（LPS）

解法：将字元串的逆序與原來字元串用特殊符号連接配接，構造字尾數組，求字尾數組中的最長公共字首，保證最長公共字首出現在特殊連接配接符号的兩端。

3 字尾數組求最長重複子串（LRS）

解法：構造字元串的字尾數組，對字尾數組排序，再兩兩比較得到最長的重複子串

4 字尾數組求最長的沒有重複字元的子串

解法：對這個字元串構造字尾數組，在每個字尾數組中，尋找沒有重複字元的最長字首，就是要找的子串。

<a></a>