原书出处
Introduction to Algorithms, Fourth Edition
32 第32章 字符串匹配
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