← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

32 第32章 字符串匹配

Fourth edition · 核验版本的摘录快照 · 导入于 2026-10-23T08:18:08.768Z

lines 10–11 terminates, l is the length of the longest common prefix of T[j:] and T[i:].

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

the sorted suffixes when COMPUTE-SUFFIX-ARRAY is run on the text hippityhoppity. Use the

此预览只包含定位所需的摘录和上下文。

原书定位详情

来源:a19c7933-4eda-4176-aebd-30fe7e1ad292

正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter032.xhtml

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea