后綴數(shù)組——字符串處理中的有力武器后綴樹(shù)的一個(gè)簡(jiǎn)單而高效的替代品當(dāng)今字符串處理研究中的熱門(mén)讓我們一同揭開(kāi)她神秘的面紗后綴數(shù)組——定義和符號(hào)字符集、字符、字符串都按照慣常的定義字符串S的長(zhǎng)度表示為len(S)字符串的下標(biāo)從1開(kāi)始到len(S)結(jié)束字符串S的第i個(gè)字符表示為S[i]從i到j(luò)這一段的子串表示為S[i..j]后綴是一種特殊的子串從某個(gè)位置i開(kāi)始到整個(gè)串的末尾結(jié)束S的從i開(kāi)頭的后綴等價(jià)于S[i..len(S)]后綴數(shù)組——定義和符號(hào)約定一個(gè)字符集Σ待處理的字符串約定為S，約定len(S)=n規(guī)定S以字符“$”結(jié)尾，即S[n]=“$”“$”小于Σ中所有的字符除了S[n]=“$”之外，S的其他字符都屬于Σ對(duì)于約定的字符串S，其i開(kāi)頭的后綴表示為Suffix(i)后綴數(shù)組——構(gòu)造方法把n個(gè)后綴當(dāng)作n個(gè)字符串，按照普通的方法進(jìn)行排序——O(n2)低效的原因——把后綴僅僅當(dāng)作普通的、獨(dú)立的字符串，忽略了后綴之間存在的有機(jī)聯(lián)系。如何構(gòu)造后綴數(shù)組?后綴數(shù)組——構(gòu)造方法倍增算法(DoublingAlgorithm)對(duì)字符串u，定義uk=u[1..k],len(u)≥ku,len(u)<k定義k-前綴比較關(guān)系<k，=k和≤k對(duì)兩個(gè)字符串u,v，u<kv當(dāng)且僅當(dāng)uk<vku=kv當(dāng)且僅當(dāng)uk=vku≤kv當(dāng)且僅當(dāng)uk≤vk后綴數(shù)組——構(gòu)造方法uvu<kv?u=kv?u≤kv?kuvu<2kv?u=2kv?u≤2kv?kk后綴數(shù)組——構(gòu)造方法把n個(gè)后綴按照k-前綴意義下的大小關(guān)系從小到大排序?qū)⑴判蚝蟮暮缶Y的開(kāi)頭位置順次放入數(shù)組SAk中，稱(chēng)為k-后綴數(shù)組用Rankk[i]保存Suffix(i)在排序中的名次，稱(chēng)數(shù)組Rankk為k-名次數(shù)組后綴數(shù)組——構(gòu)造方法利用SAk可以在O(n)時(shí)間內(nèi)求出Rankk利用Rankk可以在常數(shù)時(shí)間內(nèi)對(duì)兩個(gè)后綴進(jìn)行k-前綴意義下的大小比較后綴數(shù)組——構(gòu)造方法如果已經(jīng)求出Rankk可以在常數(shù)時(shí)間內(nèi)對(duì)兩個(gè)后綴進(jìn)行k-前綴意義下的比較可以在常數(shù)時(shí)間內(nèi)對(duì)兩個(gè)后綴進(jìn)行2k-前綴意義下的比較可以很方便地對(duì)所有的后綴在2k-前綴意義下排序采用快速排序O(nlogn)采用基數(shù)排序O(n)可以在O(n)時(shí)間內(nèi)由Rankk求出SA2k也就可以在O(n)時(shí)間內(nèi)求出Rank2k后綴數(shù)組——構(gòu)造方法直接根據(jù)首字符排序SA1Rank1O(nlogn)SA2Rank2O(n)SA4Rank4O(n)SA8Rank8O(n)……O(n)SAmRankmO(n)m=2t且m≥nO(nlogn)的操作一次O(n)的操作[logn]次總復(fù)雜度為O(nlogn)后綴數(shù)組——構(gòu)造方法當(dāng)m≥n時(shí)，對(duì)任意u=Suffix(x)，um=uSuffix(i)≤mSuffix(j)Suffix(i)≤Suffix(j)Suffix(i)<Suffix(j)SAm=SARankm=RankO(nlogn)求出SAm和Rankm可以在O(nlogn)時(shí)間內(nèi)求出后綴數(shù)組SA和名次數(shù)組Rank后綴數(shù)組——構(gòu)造方法m≥n，SAm=SARankm=Rank我們已經(jīng)在O(nlogn)的時(shí)間內(nèi)構(gòu)造出了后綴數(shù)組SA和名次數(shù)組Rank后綴數(shù)組——輔助工具僅僅靠后綴數(shù)組和名次數(shù)組有時(shí)候還不能很好地處理問(wèn)題后綴數(shù)組的最佳搭檔——LCP定義兩個(gè)字符串的最長(zhǎng)公共前綴LongestCommonPrefixlcp(u,v)=max{i|u=iv}也就是從頭開(kāi)始比較u和v的對(duì)應(yīng)字符持續(xù)相等的最遠(yuǎn)值后綴數(shù)組——輔助工具定義LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j]))也就是SA數(shù)組中第i個(gè)和第j個(gè)后綴的最長(zhǎng)公共前綴LCPTheorem對(duì)任何1≤i<j≤nLCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j}稱(chēng)j-i為L(zhǎng)CP(i,j)的“跨度”，LCPTheorem意義為：跨度大于1的LCP值可以表示成一段跨度等于1的LCP值的最小值若i>jLCP(i,j)=LCP(j,i)可以用跨度為1的LCP值來(lái)表示任何一個(gè)LCP值后綴數(shù)組——輔助工具定義LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j]))也就是SA數(shù)組中第i個(gè)和第j個(gè)后綴的最長(zhǎng)公共前綴LCPTheorem對(duì)任何1≤i<j≤nLCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j}稱(chēng)j-i為L(zhǎng)CP(i,j)的“跨度”，LCPTheorem意義為：跨度大于1的LCP值可以表示成一段跨度等于1的LCP值的最小值后綴數(shù)組——輔助工具設(shè)height[i]=LCP(i-1,i)根據(jù)LCPTheoremLCP(i,j)=min{height[k]|i+1≤k≤j}計(jì)算LCP(i,j)等價(jià)于詢問(wèn)數(shù)組height中下標(biāo)從i+1到j(luò)范圍內(nèi)所有元素的最小值經(jīng)典的RMQ(RangeMinimumQuery)問(wèn)題!!!線段樹(shù)、排序樹(shù)——O(nlogn)預(yù)處理,O(logn)每次詢問(wèn)標(biāo)準(zhǔn)RMQ方法——O(n)預(yù)處理,O(1)每次詢問(wèn)后綴數(shù)組——輔助工具采用一種“神奇的”方法，可以在O(n)時(shí)間內(nèi)計(jì)算出height數(shù)組采用標(biāo)準(zhǔn)RMQ方法在O(n)時(shí)間內(nèi)進(jìn)行預(yù)處理之后就可以在常數(shù)時(shí)間內(nèi)算出任何的LCP(i,j)根據(jù)lcp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j])可以在常數(shù)時(shí)間內(nèi)計(jì)算出任何兩個(gè)后綴的最長(zhǎng)公共前綴后綴數(shù)組——輔助工具采用一種“神奇的”方法，可以在O(n)時(shí)間內(nèi)計(jì)算出height數(shù)組采用標(biāo)準(zhǔn)RMQ方法在O(n)時(shí)間內(nèi)進(jìn)行預(yù)處理之后就可以在常數(shù)時(shí)間內(nèi)算出任何的LCP(i,j)可以在常數(shù)時(shí)間內(nèi)計(jì)算出任何兩個(gè)后綴的最長(zhǎng)公共前綴這是后綴數(shù)組最常用以及最強(qiáng)大的功能之一后綴數(shù)組——應(yīng)用舉例怎樣使用后綴數(shù)組？后綴數(shù)組——應(yīng)用舉例回文串——順讀和倒讀完全一樣的字符串奇回文串字符串u滿足：len(u)=p為奇數(shù)對(duì)任何1≤i≤(p-1)/2，u[i]=u[p-i+1]偶回文串字符串v滿足：len(v)=q為奇數(shù)對(duì)任何1≤i≤q/2，v[i]=v[q-i+1]回文串后綴數(shù)組——應(yīng)用舉例枚舉奇回文串中間一個(gè)字符的位置盡量向兩邊擴(kuò)展后綴數(shù)組——應(yīng)用舉例rrii-r-1i+r+1反射相等以某個(gè)位置為中心向兩邊擴(kuò)展的復(fù)雜度為O(m)整個(gè)算法的復(fù)雜度為O(m2)后綴數(shù)組——應(yīng)用舉例求以一個(gè)位置i為中心向兩邊擴(kuò)展的最遠(yuǎn)值是算法的核心部分需要降低這一步的復(fù)雜度后綴數(shù)組——應(yīng)用舉例$中心ii'=2m-i+2i-ri+ri'+r#求以i為中心向兩邊擴(kuò)展的最遠(yuǎn)值，等價(jià)于求Suffix(i)和Suffix(i')的最長(zhǎng)公共前綴后綴數(shù)組?。。⊥瑫r(shí)和粉紅串反射相等T串T'串Suffix(i)和Suffix(i')的公共前綴后綴數(shù)組——應(yīng)用舉例解法：初始化答案為0。按照前述方法修改串T，得到串S求出后綴數(shù)組SA、名次數(shù)組Rank計(jì)算height數(shù)組并進(jìn)行標(biāo)準(zhǔn)RMQ方法預(yù)處理復(fù)雜度：設(shè)len(S)=n，則n=2m+2O(m)+O(nlogn)+m*O(1)=O(nlogn)枚舉i，計(jì)算以i為中心向兩邊擴(kuò)展的最遠(yuǎn)值并更新答案+2*O(n)后綴數(shù)組VS后綴樹(shù)后綴樹(shù)也可以做到類(lèi)似的事情后綴數(shù)組有什么優(yōu)勢(shì)呢？后綴數(shù)組VS后綴樹(shù)后綴數(shù)組在信息學(xué)競(jìng)賽中最大的優(yōu)勢(shì)：易于理解，易于編程，易于調(diào)試后綴數(shù)組比后綴樹(shù)占用的空間少——處理長(zhǎng)字符串，如DNA分析后綴數(shù)組VS后綴樹(shù)時(shí)間復(fù)雜度的比較按照字符總數(shù)|Σ|把字符集Σ分為三種類(lèi)型：ConstantAlphabet ——|Σ|是一個(gè)常數(shù)IntegerAlphabet ——|Σ|為字符串長(zhǎng)度n的多項(xiàng)式函數(shù)GeneralAlphabet ——對(duì)|Σ|沒(méi)有任何限制ConstantAlphabetIntegerAlphabetGeneralAlphabet后綴數(shù)組VS后綴樹(shù)后綴數(shù)組是直接針對(duì)GeneralAlphabet設(shè)計(jì)的算法復(fù)雜度跟字符集的類(lèi)型沒(méi)有關(guān)系后綴樹(shù)則對(duì)不同字符集有不同的表現(xiàn)如果采用兒子-兄弟方式來(lái)表達(dá)后綴樹(shù)：構(gòu)造的復(fù)雜度為O(n*|Σ|)——顯然不適合Integer和GeneralAlphabet，對(duì)于|Σ|稍大的ConstantAlphabet也無(wú)法勝任解決方法：每個(gè)節(jié)點(diǎn)建立一棵紅黑樹(shù)來(lái)保存兒子，復(fù)雜度為O(n*log|Σ|)?！?jìng)賽的時(shí)候有時(shí)間編嗎？結(jié)論對(duì)于Integer和General以及|Σ|較大的ConstantAlphabet，后綴樹(shù)甚至在時(shí)間復(fù)雜度上都無(wú)法勝過(guò)后綴數(shù)組。但是對(duì)于|Σ|較小的ConstantAlphabet，后綴樹(shù)還是有著速度上的優(yōu)勢(shì)的?！覀円鶕?jù)實(shí)際情況，因“題”制宜選擇合適的數(shù)據(jù)結(jié)構(gòu)后綴數(shù)組——最后的話研究后綴數(shù)組，不是因?yàn)楹ε潞缶Y樹(shù)的繁瑣也沒(méi)有貶低后綴樹(shù)，抬高后綴數(shù)組的意思對(duì)于功能相似的兩個(gè)數(shù)據(jù)結(jié)構(gòu)，我們應(yīng)該靈活地掌握，有比較有選擇地使用構(gòu)造后綴數(shù)組用到的倍增思想對(duì)我們的思考也是有幫助的后綴數(shù)組謝謝大家！后綴數(shù)組——關(guān)于“$”為什么規(guī)定S以“$”結(jié)尾？后綴數(shù)組——關(guān)于“$”設(shè)u=Suffix(i)，v=Suffix(j)后綴u，以i開(kāi)頭后綴v，以i開(kāi)頭對(duì)u、v在2k-前綴意義下進(jìn)行比較kkkk比較紅色字符相當(dāng)于在k-前綴意義下比較Suffix(i)和Suffix(j)比較綠色字符相當(dāng)于在k-前綴意義下比較Suffix(i+k)和Suffix(j+k)在2k-前綴意義下比較兩個(gè)后綴可以轉(zhuǎn)化成在k-前綴意義下比較兩個(gè)后綴i+kj+k2k-前綴比較關(guān)系可以用兩個(gè)k-前綴比較關(guān)系來(lái)表達(dá)u<2kvu<kvOR(u=kvANDSuffix(i+k)<kSuffix(v,j+k))u=2kv u=kvANDSuffix(i+k)=kSuffix(j+k)u≤2kvu<kvOR(u=kvANDSuffix(i+k)≤kSuffix(j+k))后綴數(shù)組——關(guān)于“$”iji+kj+k??大于n!!$“$”小于對(duì)應(yīng)的字符不相等后綴數(shù)組——關(guān)于“$”結(jié)尾的“$”避免了下標(biāo)越界造成無(wú)意義表達(dá)式的麻煩為什么規(guī)定“$”小于Σ中的任何字符？規(guī)定“$”不等于Σ中的任何字符可以達(dá)到同樣的目的？后綴數(shù)組——關(guān)于“$”ij$相等i開(kāi)頭的后綴<j開(kāi)頭的后綴$小于對(duì)應(yīng)字符仍然能得到i開(kāi)頭的后綴<j開(kāi)頭的后綴原串新串后綴數(shù)組——關(guān)于“$”規(guī)定“$”小于Σ中的任何字符是為了保證在串S結(jié)尾添加“$”改造為S'之后，S中的后綴之間的大小關(guān)系在S'中依然成立。于是S'的后綴數(shù)組、名次數(shù)組都和S的一樣。另外不難看出S'的height數(shù)組和S的也是一樣的。在待處理的串后添加“$”不會(huì)影響結(jié)果的正確性，只是令操作變得方便。后綴數(shù)組——關(guān)于“$”后綴數(shù)組——關(guān)于“#”為什么要先在T串后加“#”然后再反射T串？后綴數(shù)組——關(guān)于“#”$中心ii'i-ri+ri'+r#T串T'串Suffix(i)和Suffix(i')的公共前綴Suffix(i)和Suffix(i')的最長(zhǎng)公共前綴不再能準(zhǔn)確地反映向兩邊擴(kuò)展的最遠(yuǎn)值因?yàn)樽筮叺臏\綠色串用到了T'中的字符這是不合實(shí)際的后綴數(shù)組——關(guān)于“#”在T的結(jié)尾加上“#”保證了Suffix(i)和Suffix(i')的最長(zhǎng)公共前綴能正確反映以i為中心向兩邊擴(kuò)展的最遠(yuǎn)值特殊判斷也可以做到這一點(diǎn)，但是加一個(gè)“#”稍微方便一些。后綴數(shù)組——關(guān)于線性算法采用Farach的構(gòu)造方法，對(duì)于IntegerAlphbet，可以在O(n)時(shí)間內(nèi)構(gòu)造出后綴樹(shù)我們不打算把Farach方法列入考察范圍這個(gè)算法實(shí)現(xiàn)極為繁瑣更像是挖空心思將幾個(gè)算法湊在一起的“大雜燴”競(jìng)賽的有限時(shí)間內(nèi)幾乎無(wú)法完成后綴數(shù)組——關(guān)于線性算法后綴數(shù)組——關(guān)于線性算法即使構(gòu)造完成了，如果想使用后綴樹(shù)，還是得想辦法處理每個(gè)節(jié)點(diǎn)指向兒子的指針。對(duì)字符總數(shù)太大的情況只能排序存儲(chǔ)時(shí)間復(fù)雜度立刻增加到O(nlog|Σ|)并沒(méi)有得到改善，也未必比后綴數(shù)組快后綴數(shù)組——關(guān)于線性算法訪問(wèn)的時(shí)候要二分查找指向兒子的指針幾乎所有的基本操作復(fù)雜度都要乘上系數(shù)log|Σ|某些情況下甚至比后綴數(shù)組差，如多模式串匹配后綴數(shù)組——關(guān)于線性算法只有極少數(shù)情況下后綴樹(shù)才能真正做到線性時(shí)間構(gòu)造，常數(shù)時(shí)間基本操作Farach構(gòu)造方法的理論價(jià)值大于它在競(jìng)賽中的實(shí)際價(jià)值不適合拿來(lái)和本文所講的后綴數(shù)組相比后綴數(shù)組——關(guān)于線性算法更令人吃驚的是后綴數(shù)組也有對(duì)IntegerAlphbet情況下線性構(gòu)造的算法這是一種三分法，比Farach方法優(yōu)美得多但是我們也無(wú)意在本文中探討后綴數(shù)組——關(guān)于線性算法雖然說(shuō)它比Farach方法優(yōu)美，但是實(shí)現(xiàn)起來(lái)仍然比倍增算法繁得多不適合在競(jìng)賽中使用有興趣的同學(xué)可以自行研究三分法的技巧性顯得較強(qiáng)與技巧相比我更加欣賞倍增算法所體現(xiàn)出的深刻思想后綴數(shù)組——關(guān)于空間從Rankk推出SAk和Rank2k需要兩個(gè)數(shù)組（共2n個(gè)整數(shù)）以實(shí)現(xiàn)基數(shù)排序同一時(shí)刻Rankk和Rank2k只需要保存一個(gè)SA2k可以直接覆蓋SAk2n個(gè)整數(shù)保存結(jié)果+2n個(gè)整數(shù)輔助計(jì)算技巧性地操作可以將輔助計(jì)算的空間減少至n個(gè)整數(shù)后綴數(shù)組——關(guān)于空間后綴樹(shù)通常有2n個(gè)以上節(jié)點(diǎn)通常每個(gè)節(jié)點(diǎn)要兩個(gè)整數(shù)，至少要保存一個(gè)整數(shù)每個(gè)節(jié)點(diǎn)兩個(gè)指針4n個(gè)指針+2n個(gè)整數(shù)至少是4n個(gè)指針