知识卡片

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

计数排序使后缀倍增每轮线性

理解等级:中级

倍增法每轮都排序n个左右秩二元组;两个秩都在0到n之间,可先按右秩、再按左秩稳定计数排序。

每轮Θ(n),约lg n轮,建后缀数组总时间Θ(n lg n)。

若改用比较排序,总界为O(n lg² n)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The values of left-rank and right-rank being sorted in line 18 are always integers in the range 0 to n. Therefore, radix sort can sort the substr-rank array in Θ(n) time by first running counting sort (see Chapter 8) based on right-rank and then running counting sort based on left-rank. Now each iteration of the while loop of lines 10–19 takes only Θ(n) time, giving a total time of Θ(n 1g n). Exercise 32.5-2 asks you to make a simple modification to COMPUTE-SUFFIX-ARRAY that allows the while loop of lines 10–19 to iterate fewer than ⌈1g n⌉ – 1 times for certain inputs. Computing the LCP array Recall that LCP[i] is defined as the length of the longest common

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[75000,80000))。 - 结论依据:原文第32.5节复杂度、LCP算法与引理,或章末问题32-1/32-2给出的定义与构造步骤。 - 原始内容:The values of left-rank and right-rank being sorted in line 18 are always integers in the range 0 to n . Therefore, radix sort can sort the substr-rank array in Θ( n ) time by first running counting sort (see Chapter 8 ) based on right-rank and then running counting sort based on left-rank . Now each iteration of the while loop of lines 10–19 takes only Θ( n ) time, giving a total time of Θ( n 1g n ). Exercise 32.5-2 asks you to make a simple modification to C OMPUTE -S UFFIX -A RRAY that allows the while loop of lines 10–19 to iterate fewer than ⌈ 1g n ⌉ – 1 times for certain inputs. Computing the LCP array Recall that LCP [ i ] is defined as the length of the longest common