知识卡片

普通读书笔记卡 · 3707.c.3

倍增排序维持片段字典序不变式

理解等级:高级

后缀数组按字典序列出文本T各后缀的起点。倍增算法为每个起点i保存长度ℓ片段T[i:i+ℓ−1]的秩;越过文本末尾的部分用小于正常字符的哨兵秩处理。

初轮由字符编码得到短片段的秩。若长度ℓ片段的秩已正确,长度2ℓ片段可拆成前、后两个长度ℓ片段,因此用秩对(rank[i], rank[i+ℓ])排序,就得到长度2ℓ片段的正确字典序和新秩。ℓ每轮翻倍;当ℓ≥n时,每个片段已覆盖从其起点到文本末尾,按秩排列的起点就是后缀数组。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第32章 字符串匹配 · 查看原书依据

      This example illuminates why the COMPUTE-SUFFIX-ARRAY procedure works. The initial ranks established in lines 2–7 are simply the ord values of the characters in the text, and so when line 8 sorts the substr-rank array, its ordering corresponds to the lexicographic ordering of the length-2 substrings. Each iteration of the while loop of lines 10–19 takes sorted substrings of length l and produces sorted substrings of length 2l. Once l reaches or exceeds n, all substrings have been sorted. Within an iteration of the while loop, the MAKE-RANKS procedure “re-ranks” the substrings that were sorted, either by line 8 before the first iteration or by line 18 in the previous iteration. MAKE-RANKS takes a substr-rank array,

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[70000,75000))。 - 结论依据:原文第32.5节后缀数组、LCP和倍增构造的定义、示例或正确性推导。 - 原始内容:This example illuminates why the C OMPUTE -S UFFIX -A RRAY procedure works. The initial ranks established in lines 2–7 are simply the ord values of the characters in the text, and so when line 8 sorts the substr-rank array, its ordering corresponds to the lexicographic ordering of the length-2 substrings. Each iteration of the while loop of lines 10–19 takes sorted substrings of length l and produces sorted substrings of length 2 l . Once l reaches or exceeds n , all substrings have been sorted. Within an iteration of the while loop, the M AKE -R ANKS procedure “re-ranks” the substrings that were sorted, either by line 8 before the first iteration or by line 18 in the previous iteration. M AKE -R ANKS takes a substr-rank array,