倍增法之后綴數(shù)組解決重復(fù)子串的問(wèn)題

周波 柳杰

【摘要】后綴數(shù)組是處理字符串的有力工具。利用后綴數(shù)組解決字符串問(wèn)題，無(wú)論是在時(shí)間復(fù)雜度和空間復(fù)雜度上，都非常有優(yōu)勢(shì)，在信息學(xué)競(jìng)賽中也是非常實(shí)用的一個(gè)工具。本文分兩部分，第一部分介紹倍增法構(gòu)造后綴數(shù)組，第二部分介紹簡(jiǎn)潔高效代碼的實(shí)現(xiàn)與應(yīng)用。

【關(guān)鍵字】字符串 后綴 后綴數(shù)組 名次數(shù)組 快速排序

后綴數(shù)組的實(shí)現(xiàn)，本節(jié)主要介紹后綴數(shù)組的倍增法實(shí)現(xiàn)。

一、基本定義

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

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

二、倍增算法

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