算法合集之《后綴數(shù)組》

后綴數(shù)組

蕪湖一中許智磊后綴數(shù)組——字符串處理中的有力武器后綴樹(shù)的一個(gè)簡(jiǎn)單而高效的替代品當(dāng)今字符串處理研究中的熱門(mén)讓我們一同揭開(kāi)她神秘的面紗算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!后綴數(shù)組——定義和符號(hào)約定一個(gè)字符集Σ待處理的字符串約定為S，約定len(S)=n規(guī)定S以字符“$”結(jié)尾，即S[n]=“$”“$”小于Σ中所有的字符除了S[n]=“$”之外，S的其他字符都屬于Σ對(duì)于約定的字符串S，其i開(kāi)頭的后綴表示為Suffix(i)算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!后綴數(shù)組——構(gòu)造方法把n個(gè)后綴當(dāng)作n個(gè)字符串，按照普通的方法進(jìn)行排序——O(n2)低效的原因——把后綴僅僅當(dāng)作普通的、獨(dú)立的字符串，忽略了后綴之間存在的有機(jī)聯(lián)系。如何構(gòu)造后綴數(shù)組?算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!后綴數(shù)組——構(gòu)造方法uvu<kv?u=kv?u≤kv?kuvu<2kv?u=2kv?u≤2kv?kk算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!后綴數(shù)組——構(gòu)造方法m≥n，SAm=SARankm=Rank我們已經(jīng)在O(nlogn)的時(shí)間內(nèi)構(gòu)造出了后綴數(shù)組SA和名次數(shù)組Rank算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!后綴數(shù)組——輔助工具設(shè)height[i]=LCP(i-1,i)根據(jù)LCPTheoremLCP(i,j)=min{height[k]|i+1≤k≤j}計(jì)算LCP(i,j)等價(jià)于詢(xún)問(wèn)數(shù)組height中下標(biāo)從i+1到j(luò)范圍內(nèi)所有元素的最小值經(jīng)典的RMQ(RangeMinimumQuery)問(wèn)題!!!線(xiàn)段樹(shù)、排序樹(shù)——O(nlogn)預(yù)處理,O(logn)每次詢(xún)問(wèn)標(biāo)準(zhǔn)RMQ方法——O(n)預(yù)處理,O(1)每次詢(xún)問(wèn)算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!后綴數(shù)組——應(yīng)用舉例怎樣使用后綴數(shù)組？算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!后綴數(shù)組——應(yīng)用舉例字符串T的回文子串——T的子串，并且是回文串字符串T的最長(zhǎng)回文子串——T的回文子串中長(zhǎng)度最大的給出一個(gè)字符串T，求它的最長(zhǎng)回文子串給出最大長(zhǎng)度即可設(shè)len(T)=m算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!后綴數(shù)組——應(yīng)用舉例枚舉奇回文串中間一個(gè)字符的位置盡量向兩邊擴(kuò)展算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!后綴數(shù)組——應(yīng)用舉例求以一個(gè)位置i為中心向兩邊擴(kuò)展的最遠(yuǎn)值是算法的核心部分需要降低這一步的復(fù)雜度算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!后綴數(shù)組VS后綴樹(shù)后綴數(shù)組在信息學(xué)競(jìng)賽中最大的優(yōu)勢(shì)：易于理解，易于編程，易于調(diào)試后綴數(shù)組比后綴樹(shù)占用的空間少——處理長(zhǎng)字符串，如DNA分析算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!后綴數(shù)組謝謝大家！算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!后綴數(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+k算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!后綴數(shù)組——關(guān)于“$”結(jié)尾的“$”避免了下標(biāo)越界造成無(wú)意義表達(dá)式的麻煩為什么規(guī)定“$”小于Σ中的任何字符？規(guī)定“$”不等于Σ中的任何字符可以達(dá)到同樣的目的？算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!后綴數(shù)組——關(guān)于“$”規(guī)定“$”小于Σ中的任何字符是為了保證在串S結(jié)尾添加“$”改造為S'之后，S中的后綴之間的大小關(guān)系在S'中依然成立。于是S'的后綴數(shù)組、名次數(shù)組都和S的一樣。另外不難看出S'的height數(shù)組和S的也是一樣的。算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!后綴數(shù)組——關(guān)于“#”為什么要先在T串后加“#”然后再反射T串？算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!后綴數(shù)組——關(guān)于“#”在T的結(jié)尾加上“#”保證了Suffix(i)和Suffix(i')的最長(zhǎng)公共前綴能正確反映以i為中心向兩邊擴(kuò)展的最遠(yuǎn)值特殊判斷也可以做到這一點(diǎn)，但是加一個(gè)“#”稍微方便一些。算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!這個(gè)算法實(shí)現(xiàn)極為繁瑣更像是挖空心思將幾個(gè)算法湊在一起的“大雜燴”競(jìng)賽的有限時(shí)間內(nèi)幾乎無(wú)法完成后綴數(shù)組——關(guān)于線(xiàn)性算法算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!后綴數(shù)組——關(guān)于線(xiàn)性算法訪(fǎng)問(wèn)的時(shí)候要二分查找指向兒子的指針幾乎所有的基本操作復(fù)雜度都要乘上系數(shù)log|Σ|某些情況下甚至比后綴數(shù)組差，如多模式串匹配算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!后綴數(shù)組——關(guān)于線(xiàn)性算法更令人吃驚的是后綴數(shù)組也有對(duì)IntegerAlphbet情況下線(xiàn)性構(gòu)造的算法這是一種三分法，比Farach方法優(yōu)美得多但是我們也無(wú)意在本文中探討算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!后綴數(shù)組——關(guān)于空間為什么不算上height數(shù)組和RMQ預(yù)處理的空間？——為了處理問(wèn)題，后綴樹(shù)需要預(yù)處理以便計(jì)算節(jié)點(diǎn)的最近公共祖先（LeastCommonAncestor）LCA問(wèn)題和RMQ問(wèn)題是等價(jià)的后綴樹(shù)預(yù)處理的空間占用和后綴數(shù)組基本一樣算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!后綴數(shù)組——關(guān)于RMQ采用對(duì)待詢(xún)問(wèn)數(shù)組建立Treap的方法轉(zhuǎn)化為0-1RMQ采用模板方法將復(fù)雜度降為線(xiàn)性競(jìng)賽中用O(nlogn)預(yù)處理的方法已經(jīng)足夠算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第32頁(yè)!后綴數(shù)組——關(guān)于倍增思想關(guān)鍵在于找到2k到2k+1轉(zhuǎn)換的橋梁本文中的橋梁就是2k-前綴比較關(guān)系可以轉(zhuǎn)化為k-前綴比較關(guān)系算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第33頁(yè)!后綴數(shù)組——關(guān)于倍增思想《道德經(jīng)》云：道生一，一生二，二生三，三生萬(wàn)物是否能用好倍增思想，做到：一生二，二生四，四生八，……要看各人的道行如何了算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第34頁(yè)!后綴數(shù)組——定義和符號(hào)字符串的大小關(guān)系按照通常所說(shuō)的“字典順序”進(jìn)行比較我們對(duì)S的n個(gè)后綴按照字典順序從小到大排序?qū)⑴判蚝蟮暮缶Y的開(kāi)頭位置順次放入數(shù)組SA中，稱(chēng)為后綴數(shù)組令Rank[i]保存Suffix(i)在排序中的名次，稱(chēng)數(shù)組Rank為名次數(shù)組算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第35頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第36頁(yè)!后綴數(shù)組——構(gòu)造方法設(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+k算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第37頁(yè)!后綴數(shù)組——構(gòu)造方法利用SAk可以在O(n)時(shí)間內(nèi)求出Rankk利用Rankk可以在常數(shù)時(shí)間內(nèi)對(duì)兩個(gè)后綴進(jìn)行k-前綴意義下的大小比較算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第38頁(yè)!后綴數(shù)組——構(gòu)造方法1-前綴比較關(guān)系實(shí)際上是對(duì)字符串的個(gè)字符進(jìn)行比較可以直接根據(jù)開(kāi)頭字符對(duì)所有后綴進(jìn)行排序求出SA1采用快速排序，復(fù)雜度為O(nlogn)然后根據(jù)SA1在O(n)時(shí)間內(nèi)求出Rank1可以在O(nlogn)時(shí)間內(nèi)求出SA1和Rank1算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第39頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第40頁(yè)!后綴數(shù)組——方法總結(jié)利用到后綴之間的聯(lián)系用k-前綴比較關(guān)系來(lái)表達(dá)2k-前綴比較關(guān)系每次可以將參與比較的前綴長(zhǎng)度加倍根據(jù)SAk、Rankk求出SA2k、Rank2k參與比較的前綴長(zhǎng)度達(dá)到n以上時(shí)結(jié)束倍增思想算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第41頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第42頁(yè)!后綴數(shù)組——輔助工具4=LCP(i,i+1)3=LCP(i+1,i+2)5=LCP(i+2,j)LCP(i,j)=3Suffix(SA[i])Suffix(SA[j])Suffix(SA[i+1])Suffix(SA[i+2])算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第43頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第44頁(yè)!后綴數(shù)組——應(yīng)用舉例幾個(gè)常見(jiàn)的問(wèn)題問(wèn)題一給定一個(gè)字符串S，對(duì)它的所有后綴進(jìn)行排序。問(wèn)題二給定一個(gè)待匹配串S，每次輸入一個(gè)模式串P，要求返回P在S中的一個(gè)匹配的開(kāi)頭位置，或者返回?zé)o匹配。問(wèn)題三給定一個(gè)字符串S，求出S中的最長(zhǎng)回文子串。O(n2)O(m+n)O(n2)O(nlogn)O(m+logn)O(nlogn)算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第45頁(yè)!后綴數(shù)組——應(yīng)用舉例回文串——順讀和倒讀完全一樣的字符串奇回文串字符串u滿(mǎn)足：len(u)=p為奇數(shù)對(duì)任何1≤i≤(p-1)/2，u[i]=u[p-i+1]偶回文串字符串v滿(mǎn)足：len(v)=q為奇數(shù)對(duì)任何1≤i≤q/2，v[i]=v[q-i+1]回文串算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第46頁(yè)!后綴數(shù)組——應(yīng)用舉例分析求最長(zhǎng)奇回文子串的算法最長(zhǎng)偶回文子串可以類(lèi)似求出算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第47頁(yè)!后綴數(shù)組——應(yīng)用舉例rrii-r-1i+r+1反射相等以某個(gè)位置為中心向兩邊擴(kuò)展的復(fù)雜度為O(m)整個(gè)算法的復(fù)雜度為O(m2)算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第48頁(yè)!后綴數(shù)組——應(yīng)用舉例$中心ii'=2m-i+2i-ri+ri'+r#求以i為中心向兩邊擴(kuò)展的最遠(yuǎn)值，等價(jià)于求Suffix(i)和Suffix(i')的最長(zhǎng)公共前綴后綴數(shù)組?。?！同時(shí)和粉紅串反射相等T串T'串Suffix(i)和Suffix(i')的公共前綴算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第49頁(yè)!后綴數(shù)組VS后綴樹(shù)后綴樹(shù)也可以做到類(lèi)似的事情后綴數(shù)組有什么優(yōu)勢(shì)呢？算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第50頁(yè)!后綴數(shù)組VS后綴樹(shù)時(shí)間復(fù)雜度的比較按照字符總數(shù)|Σ|把字符集Σ分為三種類(lèi)型：ConstantAlphabet ——|Σ|是一個(gè)常數(shù)IntegerAlphabet ——|Σ|為字符串長(zhǎng)度n的多項(xiàng)式函數(shù)GeneralAlphabet ——對(duì)|Σ|沒(méi)有任何限制ConstantAlphabetIntegerAlphabetGeneralAlphabet算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第51頁(yè)!后綴數(shù)組——最后的話(huà)研究后綴數(shù)組，不是因?yàn)楹ε潞缶Y樹(shù)的繁瑣也沒(méi)有貶低后綴樹(shù)，抬高后綴數(shù)組的意思對(duì)于功能相似的兩個(gè)數(shù)據(jù)結(jié)構(gòu)，我們應(yīng)該靈活地掌握，有比較有選擇地使用構(gòu)造后綴數(shù)組用到的倍增思想對(duì)我們的思考也是有幫助的算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第52頁(yè)!后綴數(shù)組——關(guān)于“$”為什么規(guī)定S以“$”結(jié)尾？算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第53頁(yè)!2k-前綴比較關(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第54頁(yè)!后綴數(shù)組——關(guān)于“$”ij$相等i開(kāi)頭的后綴<j開(kāi)頭的后綴$小于對(duì)應(yīng)字符仍然能得到i開(kāi)頭的后綴<j開(kāi)頭的后綴原串新串算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第55頁(yè)!在待處理的串后添加“$”不會(huì)影響結(jié)果的正確性，只是令操作變得方便。后綴數(shù)組——關(guān)于“$”算法合集之《后綴數(shù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第56頁(yè)!后綴數(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ù)組》共66頁(yè)，您現(xiàn)在瀏覽的是第57頁(yè)!后綴數(shù)組——關(guān)于線(xiàn)性算法采用Farach的構(gòu)造方法，對(duì)于IntegerAlphbet，可以在O(n)時(shí)間內(nèi)構(gòu)造出后綴樹(shù)我們不打算把Farach方法列入考察范圍算法合集之《后