← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

32 第32章 字符串匹配

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

ation because of line 9. Lines 5–8 adjust k so that it becomes the correct value of π[q].

The while loop of lines 5–6 searches through all values k ∈ π*[q – 1] in decreasing order to find the value of π[q]. The loop terminates either because k reaches 0 or P[k + 1] = P[q]. Because the “and” operator short-circuits, if the loop terminates because P[k + 1] = P[q], then k must have also been positive, and so k is the greatest value in Eq–1. In this case, lines 7–9 set π[q] to k + 1, according to Corollary 32.7. If, instead, the while loop terminates because k = 0, then there are two possibilities. If P[1] = P[q], then Eq–1 = {0}, and lines 7–9 set both k and π[q] to 1. If k

= 0 and P[1] ≠ P[q], however, then Eq–1 = ø;. In this case, line 9 sets π[q] to 0, again

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

原书定位详情

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

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

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea