對(duì)于后綴數(shù)組的概念，很多人都存在疑惑，為什么要學(xué)習(xí)后綴數(shù)組？那么我們就來說說原因，后綴數(shù)組是一個(gè)比較強(qiáng)大的處理字符串的算法，是有關(guān)字符串的基礎(chǔ)算法，所以必須掌握。 

學(xué)會(huì)后綴自動(dòng)機(jī)(SAM)就不用學(xué)后綴數(shù)組(SA)了？不，雖然SAM看起來更為強(qiáng)大和全面，但是有些SAM解決不了的問題能被SA解決，只掌握SAM是遠(yuǎn)遠(yuǎn)不夠的。 

……

有什么SAM做不了的例子？ 

比如果求一個(gè)串后綴的lcp方面的應(yīng)用，這是SA可以很方便的用rmq來維護(hù)，但是SAM還要求lca，比較麻煩，還有就是字符集比較大的時(shí)候SA也有優(yōu)勢(shì)。 

在計(jì)算機(jī)科學(xué)里, 后綴數(shù)組（suffix array）是一個(gè)通過對(duì)字符串的所有后綴經(jīng)過排序后得到的數(shù)組。此數(shù)據(jù)結(jié)構(gòu)被運(yùn)用于全文索引、數(shù)據(jù)壓縮算法、以及生物信息學(xué)。

后綴數(shù)組被烏迪·曼伯爾與尤金·邁爾斯于1990年提出，作為對(duì)后綴樹的一種替代，更簡(jiǎn)單以及節(jié)省空間。它們也被Gaston Gonnet 于1987年獨(dú)立發(fā)現(xiàn)，并命名為“PAT數(shù)組”。

后綴數(shù)組（Suffix Array）本質(zhì)上是對(duì)一個(gè)字符串的所有后綴進(jìn)行排序，之后會(huì)得到兩個(gè)信息，分別是：

（1）SA[i]，表示排名為 i 的后綴的起始位置。

（2）Rank[i]，表示起始位置為 i 的后綴的排名。

SA數(shù)組和Rank 數(shù)組是類似反函數(shù)的關(guān)系，有：SA[Rank[i]]=Rank[SA[i]]=iSA[Rank[i]]=Rank[SA[i]]=i，也就是說如果我求出了其中一個(gè)數(shù)組，就可以很快知道另一個(gè)數(shù)組。利用這兩個(gè)信息，可以處理很多字符串相關(guān)的問題。

構(gòu)造后綴數(shù)組——SA

先定義一些變量的含義

Str ：需要處理的字符串(長(zhǎng)度為L(zhǎng)en) 

Suffix[i] ：Str下標(biāo)為i ~ Len的連續(xù)子串(即后綴) 

Rank[i] : Suffix[i]在所有后綴中的排名 

SA[i] : 滿足Suffix[SA[1]] < Suffix[SA[2]] …… < Suffix[SA[Len]],即排名為i的后綴為Suffix[SA[i]] (與Rank是互逆運(yùn)算) 

好，來形象的理解一下 

后綴數(shù)組指的就是這個(gè)SA[i]，有了它，我們就可以實(shí)現(xiàn)一些很強(qiáng)大的功能(如不相同子串個(gè)數(shù)、連續(xù)重復(fù)子串等)。如何快速的到它，便成為了這個(gè)算法的關(guān)鍵。而SA和Rank是互逆的，只要求出任意一個(gè)，另一個(gè)就可以O(shè)(Len)得到。 

現(xiàn)在比較主流的算法有兩種，倍增和DC3，在這里，就主要講一下稍微慢一些，但比較好實(shí)現(xiàn)以及理解的倍增算法(雖說慢，但也是O(Len logLen)的。

構(gòu)造最長(zhǎng)公共前綴——Height

同樣先是定義一些變量

Heigth[i] : 表示Suffix[SA[i]]和Suffix[SA[i - 1]]的最長(zhǎng)公共前綴，也就是排名相鄰的兩個(gè)后綴的最長(zhǎng)公共前綴 

H[i] : 等于Height[Rank[i]]，也就是后綴Suffix[i]和它前一名的后綴的最長(zhǎng)公共前綴 

而兩個(gè)排名不相鄰的最長(zhǎng)公共前綴定義為排名在它們之間的Height的最小值。 

跟上面一樣，先形像的理解一下： 

高效地得到Height數(shù)組

如果一個(gè)一個(gè)數(shù)按SA中的順序比較的話復(fù)雜度是O(N2)級(jí)別的，想要快速的得到Height就需要用到一個(gè)關(guān)于H數(shù)組的性質(zhì)。 

H[i] ≥ H[i - 1] - 1! 

如果上面這個(gè)性質(zhì)是對(duì)的，那我們可以按照H[1]、H[2]……H[Len]的順序進(jìn)行計(jì)算，那么復(fù)雜度就降為O(N)了！ 

讓我們嘗試一下證明這個(gè)性質(zhì) : 設(shè)Suffix[k]是排在Suffix[i - 1]前一名的后綴，則它們的最長(zhǎng)公共前綴是H[i - 1]。都去掉第一個(gè)字符，就變成Suffix[k + 1]和Suffix[i]。如果H[i - 1] = 0或1,那么H[i] ≥ 0顯然成立。否則，H[i] ≥ H[i - 1] - 1(去掉了原來的第一個(gè),其他前綴一樣相等)，所以Suffix[i]和在它前一名的后綴的最長(zhǎng)公共前綴至少是H[i - 1] - 1。 

H求出來，那Height就相應(yīng)的求出來了，這樣結(jié)合SA，Rank和Height我們就可以做很多關(guān)于字符串的題了！