后綴數(shù)組就是將字符串所有后綴排序后的數(shù)組，設(shè)字符串為S，令后綴Suffix(i)表示S[i..len(S)]。用兩個(gè)數(shù)組記錄所有后綴的排序結(jié)果：

• Rank[i]記錄Suffix(i)排序后的序號(hào)，即Suffix[i]在所有后綴中是第Rank[i]小的后綴

• SA[i]記錄第i位后綴的首字母位置，即Suffix[SA[i]]在所有后綴中是第i小的后綴

然后就是怎么快速求所有后綴的順序了，其中的關(guān)鍵是如何減少兩個(gè)后綴比較的復(fù)雜度
方法是倍增法，定義一個(gè)字符串的k-前綴為該字符串的前k個(gè)字符組成的串，關(guān)于在k-后綴上的定義Suffix(k,i)、SA[k,i]和Rank[k,i]類似于前，則有

• 若Rank[k,i]＝Rank[k,j]且Rank[k,i+k]＝Rank[k,j+k]，則Suffix[2k,i]＝Suffix[2k,j]
• 若Rank[k,i]＝Rank[k,j]且Rank[k,i+k]<Rank[k,j+k]，則Suffix[2k,i]<Suffix[2k,j]
• 若Rank[k,i]<Rank[k,j]，則Suffix[2k,i]<Suffix[2k,j]

這樣就能在常數(shù)時(shí)間內(nèi)比較Suffix(2^k, i)之間的大小，從而對(duì)Suffix(2^k,i)時(shí)行排序，最后當(dāng)2^k>n時(shí)，Suffix(2^k, i)之間的大小即為所有后綴之間的大小

于是求出了所有后綴的排序，有什么用呢？主要是用于求它們之間的最長公共前綴（Longest Common Prefix，LCP）

令LCP(i,j)為第i小的后綴和第j小的后綴（也就是Suffix(SA[i])和Suffix(SA[j])）的最長公共前綴的長度，則有如下兩個(gè)性質(zhì)：

對(duì)任意i<=k<=j，有LCP(i,j) = min(LCP(i,k),LCP(k,j))

LCP(i,j)=min(i<k<=j)(LCP(k-1,k))

第一個(gè)性質(zhì)是顯然的，它的意義在于可以用來證明第二個(gè)性質(zhì)。第二個(gè)性質(zhì)的意義在于提供了一個(gè)將LCP問題轉(zhuǎn)換為RMQ問題的方法：
令height[i]＝LCP(i-1,i)，即height[i]代表第i小的后綴與第i-1小的后綴的LCP，則求LCP(i,j)就等于求height[i+1]~height[j]之間的RMQ，套用RMQ算法就可以了，復(fù)雜度是預(yù)處理O(nlogn)，查詢O(1)

然后height的求法要用到另一個(gè)數(shù)組：令h[i]=height[Rank[i]]，即h[i]表示Suffix(i)的height值（同時(shí)height[i]就表示Suffix(SA[i])的height值），則有height[i]=h[SA[i]]
然后h[i]有個(gè)性質(zhì)：

• h[i] >= h[i-1]-1

用這個(gè)性質(zhì)我們?cè)谟?jì)算h[i]的時(shí)候進(jìn)行后綴比較時(shí)只需從第h[i-1]位起比較，從而總的比較的復(fù)雜度是O(n)，也就是說h數(shù)組在O(n)的時(shí)間內(nèi)解決了。求出了h數(shù)組，根據(jù)關(guān)系式height[i]=h[SA[i]]可以在O(n)時(shí)間內(nèi)求出height數(shù)組，于是可以在O(n)時(shí)間內(nèi)求出height數(shù)組，從而整個(gè)LCP問題就解決了^_^

然后后綴數(shù)組的應(yīng)用就是利用它的LCP在需要字符串比較時(shí)降低復(fù)雜度。同時(shí)由于后綴數(shù)組的有序性可以很方便地使用二分

于是總結(jié)一下要點(diǎn)：

• 利用倍增算法在O(nlogn)的時(shí)間內(nèi)對(duì)后綴數(shù)組進(jìn)行排序
• 利用h數(shù)組的性質(zhì)在O(n)的時(shí)間內(nèi)求出儲(chǔ)存排序后相鄰后綴間的LCP數(shù)的組height
• 利用LCP的性質(zhì)將平凡LCP問題轉(zhuǎn)化為height數(shù)組上的RMQ問題

本題是求兩字符串的最長公告子串（注意是子串不是子序列），構(gòu)造出SA,RA和HEIGHT后，答案就是最大的HEIGHT，但這個(gè)最大的HEIGHT可能是同一個(gè)串中的，

所以這個(gè)最大的HEIGHT同時(shí)要滿足sa[i-1]和sa[i]不在同一個(gè)串中。

轉(zhuǎn)載于:https://www.cnblogs.com/ACAC/archive/2010/05/24/1743092.html

總結(jié)

以上是生活随笔為你收集整理的转一个后缀数组的简单总结：的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。