原书出处
Introduction to Algorithms, Fourth Edition
32 第32章 字符串匹配
res. Then we’ll prove them correct, which will be more complicated. Running-time analysis
The running time of COMPUTE-PREFIX-FUNCTION is Θ(m), which we show by using the aggregate method of amortized analysis (see Section 16.1). The only tricky part is showing that the while loop of lines 5–6 executes O(m) times altogether. Starting with some observations about k, we’ll show that it makes at most m–1 iterations. First, line 3 starts k at 0, and the only way that k increases is by the increment operation in line 8, which executes at most once per iteration of the for loop of lines 4–9. Thus, the total increase in k is at most m
–1. Second, since k < q upon entering the for loop and each iteration of the loop incremen
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter032.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea