← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

32 第32章 字符串匹配

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

≤ σ(x), since σ(x) is the largest k such that P[:k] ⊐ x, and thus σ(xa) = r ≤ σ(x) + 1. ▪

Lemma 32.3 (Suffix-function recursion lemma) For any string x and character a, if q = σ(x), then σ(xa) = σ(P[:q]a). Proof The definition of σ gives that P[:q] ⊐ x. As Figure 32.8 shows, we also have P[:q]a ⊐ xa. Let r = σ(xa). Then P[:r] ⊐ xa and, by Lemma 32.2, r ≤ q + 1. Thus, we have |P[:r]| = r ≤ q + 1 = |P[:q]a|. Since P[:q]a ⊐ xa, P[:r] ⊐ xa, and |P[:r]| ≤ |P[:q]a|, Lemma

32.1 on page 959 implies that P[:r] ⊐ P[:q]a. Therefore, r ≤ (P[:q]a), that is, σ(xa) ≤ σ

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

原书定位详情

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

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

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea