知识卡片

普通读书笔记卡 · 3707.c

后缀排序按倍增长度复用秩

理解等级:中级

倍增算法先按长度2的片段排序,再把已排序的长度l片段的秩组成左右二元组,排序得到长度至多2l片段的次序。

每轮长度翻倍;当覆盖n个字符时,次序就是后缀次序。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The procedure makes several passes over the text, with the substring length doubling each time. By the ⌈1g n⌉th pass, the procedure is sorting all the suffixes, thereby gaining the information needed to construct the suffix array. The key to attaining an O(n 1g n)-time algorithm will be to have each pass after the first sort in linear time, which will indeed be possible by using radix sort. Let’s start with a simple observation. Consider any two

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[65000,70000))。 - 结论依据:原文第32.5节后缀数组、LCP和倍增构造的定义、示例或正确性推导。 - 原始内容:The procedure makes several passes over the text, with the substring length doubling each time. By the ⌈ 1g n ⌉ th pass, the procedure is sorting all the suffixes, thereby gaining the information needed to construct the suffix array. The key to attaining an O ( n 1g n )-time algorithm will be to have each pass after the first sort in linear time, which will indeed be possible by using radix sort. Let’s start with a simple observation. Consider any two