算法合集之后綴數(shù)組(編輯修改稿)
2025-06-17 22:06 本頁面
【文章內(nèi)容簡(jiǎn)介】 組 SA 和 名次數(shù)組 Rank 后綴數(shù)組 ——方法總結(jié) 利用到后綴之間的聯(lián)系 用 k前綴比較關(guān)系來表達(dá) 2k前綴比較關(guān)系 每次可以將參與比較的前綴長(zhǎng)度加倍 根據(jù) SAk、 Rankk求出 SA2k、 Rank2k 參與比較的前綴長(zhǎng)度達(dá)到 n以上時(shí)結(jié)束 倍增思想 后綴數(shù)組 ——輔助工具 僅僅靠后綴數(shù)組和名次數(shù)組 有時(shí)候還不能很好地處理問題 后綴數(shù)組的最佳搭檔 ——LCP 定義兩個(gè)字符串的最長(zhǎng)公共前綴 Longest Common Prefix lcp(u,v)=max{i|u=iv} 也就是從頭開始比較 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)公共前綴 LCP Theorem 對(duì)任何 1≤ij≤n LCP(i,j)=min{LCP(k1,k) | i+1≤k≤j} 稱 ji為 LCP(i,j)的“ 跨度 ”， LCP Theorem意義為： 跨度大于 1的 LCP值可以表示成一段 跨度等于 1的 LCP值的 最小值 后綴數(shù)組 ——輔助工具 4=LCP(i,i+1) 3=LCP(i+1,i+2) 5=LCP(i+2,j) LCP(i,j)=3 Suffix(SA[i]) Suffix(SA[j]) Suffix(SA[i+1]) Suffix(SA[i+2]) 后綴數(shù)組 ——輔助工具 設(shè) height[i]=LCP(i1,i) 根據(jù) LCP Theorem LCP(i,j)=min{height[k] | i+1≤k≤j} 計(jì)算 LCP(i,j)等價(jià)于 詢問數(shù)組 height中下標(biāo)從 i+1 到 j 范圍內(nèi)所有元素的 最小值 經(jīng)典的 RMQ (Range Minimum Query)問題 !!! ?線段樹、排序樹 —— O(nlogn)預(yù)處理 , O(logn)每次詢問 ?標(biāo)準(zhǔn) RMQ方法 —— O(n)預(yù)處理 , O(1)每次詢問 后綴數(shù)組 ——輔助工具 采用一種“神奇的”方法，可以在 O(n)時(shí)間內(nèi)計(jì)算出 height數(shù)組 采用標(biāo)
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1