知识卡片

普通读书笔记卡 · 3707.a.2.a.1

LCP线性算法用增减量摊还

理解等级:中级

COMPUTE-LCP中匹配长度l每次循环比较成功只加1,处理下个文本起点前至多减1,并始终小于n。因此成功比较总次数少于2n;两个外层线性循环加上这些比较,使总时间Θ(n)。

这张卡片看不懂?

已有反馈 · 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

    参考来源

    - 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[80000,85000))。 - 结论依据:原文第32.5节复杂度、LCP算法与引理,或章末问题32-1/32-2给出的定义与构造步骤。 - 原始内容:As a simple aggregate analysis shows, the C OMPUTE -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 2 n times. Thus, C OMPUTE -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