知识卡片
计数排序使后缀倍增每轮线性
倍增法每轮都排序n个左右秩二元组;两个秩都在0到n之间,可先按右秩、再按左秩稳定计数排序。
每轮Θ(n),约lg n轮,建后缀数组总时间Θ(n lg n)。
若改用比较排序,总界为O(n lg² n)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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