倍增法之后綴數組解決重復子串的問題

周波 柳杰

【摘要】后綴數組是處理字符串的有力工具。利用后綴數組解決字符串問題，無論是在時間復雜度和空間復雜度上，都非常有優勢，在信息學競賽中也是非常實用的一個工具。本文分兩部分，第一部分介紹倍增法構造后綴數組，第二部分介紹簡潔高效代碼的實現與應用。

【關鍵字】字符串 后綴 后綴數組 名次數組 快速排序

后綴數組的實現，本節主要介紹后綴數組的倍增法實現。

一、基本定義

簡單的說，后綴數組是“排第幾的后綴串首字母在哪里？”，名次數組是“后綴串排第幾？”。容易看出，后綴數組和名次數組為互逆運算。如圖1所示。

設字符串的長度為n。為了方便比較大小，可以在字符串后面添加一個字符，這個字符沒有在前面的字符中出現過，而且比前面的字符都要小。在求出名次數組后，可以僅用0（1）的時間比較任意兩個后綴的大小。在求出后綴數組或名次數組中的其中一個以后，便可以用0㈤的時間求出另外一個。任意兩個后綴如果直接比較大小，最多需要比較字符n次，也就是說最遲在比較第n個字符時一定能分出“勝負”。

二、倍增算法

倍增算法的主要思路是：用倍增的方法對每個字符開始的長度為2k的子字符串進行排序，求出排名，即rank值。k從0開始，每次加1，當2k大于n以后，每個字符開始的長度為2k的子字符串便相當于所有的后綴。并且這些子字符串都一定已經比較出大小，即rank值中沒有相同的值，那么此時的rank值就是最后的結果。每一次排序都利用上次長度的字符串的rank值，那么長度為2k的字符串就可以用兩個長度為2k-1的字符串的排名作為關鍵字表示，然后進行排序，便得出了長度為2k的字符串的rank值。以字符串“aabaaaab”為例，整個過程如圖2所示。其中x、y是表示長度為2k的字符串的兩個關鍵字。