知识卡片
LCP线性算法用增减量摊还
COMPUTE-LCP中匹配长度l每次循环比较成功只加1,处理下个文本起点前至多减1,并始终小于n。因此成功比较总次数少于2n;两个外层线性循环加上这些比较,使总时间Θ(n)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
As a simple aggregate analysis shows, the COMPUTE-LCP procedure runs in Θ(n) time. Each of the two for loops iterates n times, and so it remains only to bound the total number of iterations by the while loop of lines 10–11. Each iteration increases l by 1, and the test m + l ≤ n ensures that l is always less than n. Because l has an initial value of 0 and decreases at most n – 1 times in line 14, line 11 increments l fewer than 2n times. Thus, COMPUTE-LCP takes Θ(n) time. Exercises 32.5-1 Show the substr-rank and rank arrays before each iteration of the while loop of lines 10–19 and after the last iteration of the while loop, the suffix array SA returned, and