1、處理字符串的有力工具-,華南師范大學(xué)附屬中學(xué) 羅穗騫 指導(dǎo)教師：張學(xué)東,后綴數(shù)組,目錄,第一部分 后綴數(shù)組的實(shí)現(xiàn) DC3算法 第二部分 后綴數(shù)組的應(yīng)用 例1: 求兩個(gè)字符串的最長公共子串,基本定義,【后綴數(shù)組SA】后綴數(shù)組保存的是一個(gè)字符串的所有后綴的排序結(jié)果。其中SAi保存的是字符串所有的后綴中第i小的后綴的開頭位置。 【名次數(shù)組Rank】名次數(shù)組Ranki保存的是后綴i在所有后綴中從小到大排列的“名次”。 為了敘述方便，以第k個(gè)字符開始的后綴稱為后綴k。,基本定義,以字符串“aabaaaab”為例。,DC3算法,復(fù)雜 難以實(shí)現(xiàn),僅40行代碼,DC3算法,（1）、先將后綴分成兩部分，然后對(duì)第

2、一部分的后綴排序。 （2）、利用（1）的結(jié)果，對(duì)第二部分的后綴排序。 （3）、將（1）和（2）的結(jié)果合并，即完成對(duì)所有后綴排序。,（1）、將后綴分成兩部分,字符的編號(hào)從0開始。 將后綴分成兩部分： 第一部分是后綴k（k模3不等于0） 第二部分是后綴k（k模3等于0）,對(duì)第一部分的后綴排序。,為了方便接下來的操作，這里要求字符串必須以一個(gè)最小的字符結(jié)尾。,suffix(1),suffix(2),遞歸,后綴數(shù)組,步驟（1）完成,DC3算法,（1）、先將后綴分成兩部分，然后對(duì)第一部分的后綴排序。 （2）、利用（1）的結(jié)果，對(duì)第二部分的后綴排序。 （3）、將（1）和（2）的結(jié)果合并，即完成對(duì)所有后綴排

3、序。,（2）、對(duì)第二部分的后綴排序,第一關(guān)鍵字,第二關(guān)鍵字,基數(shù)排序即可,步驟（2）完成,DC3算法,（1）、先將后綴分成兩部分，然后對(duì)第一部分的后綴排序。 （2）、利用（1）的結(jié)果，對(duì)第二部分的后綴排序。 （3）、將（1）和（2）的結(jié)果合并，即完成對(duì)所有后綴排序。,（3）、將(1)和(2)的結(jié)果合并,每次的比較都可以高效的完成,步驟（3）完成,算法分析,假設(shè)這個(gè)算法的時(shí)間復(fù)雜度為f(n)。 第（1）步排序的時(shí)間為O(n)（一般來說，m比較小，這里忽略不計(jì)）,新的字符串的長度不超過2n/3，求新字符串的sa的時(shí)間為f(2n/3)。 第（2）和第（3）步的時(shí)間都是O(n)。,算法分析,f(n)

4、= O(n) + f(2n/3) f(n) cn + f(2n/3) f(n)cn+c(2n/3)+c(4n/9)+3cn 所以 f(n)=O(n) 由此看出，DC3算法是一個(gè)優(yōu)秀的線性算法！,后綴數(shù)組的應(yīng)用,例1：如果字符串L同時(shí)出現(xiàn)在字符串A和字符串B中，則稱字符串L是字符串A和字符串B的公共子串。 給定兩個(gè)字符串A和B，求最長公共子串。 例如：字符串“aaaba”和“abaa”的最長公共子串為“aba”,height數(shù)組,定義 heighti=suffix(sai-1)和suffix(sai)的最長公共前綴，也就是排名相鄰的兩個(gè)后綴的最長公共前綴。 那么對(duì)于j和k，不妨設(shè)rankjran

5、kk,則有以下性質(zhì)：,height數(shù)組,suffix(j)和suffix(k)的最長公共前綴為heightrankj+1, heightrankj+2, heightrankj+3, ,heightrankk中的最小值。 例如，字符串為“aabaaaab”，求后綴“abaaaab”和后綴“aaab”的最長公共前綴。,例1 最長公共子串,字符串的任何一個(gè)子串都是這個(gè)字符串的某個(gè)后綴的前綴。求A和B的最長公共子串等價(jià)于求A的后綴和B的后綴的最長公共前綴的最大值。 將第二個(gè)字符串寫在第一個(gè)字符串后面，中間用一個(gè)沒有出現(xiàn)過的字符隔開，再求這個(gè)新的字符串的后綴數(shù)組。,如何高效的計(jì)算height數(shù)組？,如

6、果按height2，height3，heightn的順序計(jì)算，最壞情況下時(shí)間復(fù)雜度為O(n2)。這樣做并沒有利用字符串的性質(zhì)。定義hi=heightranki，也就是suffix(i)和在它前一名的后綴的最長公共前綴。h數(shù)組有以下性質(zhì)：,hihi-1-1,最長公共前綴為hi-1,最長公共前綴至少為hi-1-1,如何高效的計(jì)算height數(shù)組？,按照h1,h2,hn的順序計(jì)算,并利用h數(shù)組的性質(zhì)，時(shí)間復(fù)雜度可以降為O(n)。,例1 最長公共子串,（1）連接兩個(gè)字符串 （2）求后綴數(shù)組 （3）求height數(shù)組 （4）求排名相鄰但原來不在同一個(gè)字符串中的兩個(gè)后綴的height值的最大值。 時(shí)間復(fù)雜度已經(jīng)取到下限，由此看出，這是一個(gè)非常優(yōu)秀的算法。,O(|A|+|B|),總結(jié),后綴數(shù)組是字符串處理中非常優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)，是一種處理字符串問題的有力工具。 我們應(yīng)該掌握好后綴數(shù)組這種數(shù)據(jù)結(jié)構(gòu)，并且能在不同類型的題目中靈活、高效的運(yùn)用。,更多內(nèi)容,第一部分 后綴數(shù)組的實(shí)現(xiàn) (1) 倍增算法 時(shí)間復(fù)雜度O(nlogn) (2) DC3算法 時(shí)間復(fù)雜度O(n) 第二部分 后綴數(shù)組