← 返回卡片

原书出处

Introduction to Algorithms, Fourth Edition

32 第32章 字符串匹配

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

if it has just read the pattern P. We start with two lemmas about the suffix function σ.

Lemma 32.2 (Suffix-function inequality) For any string x and character a, we have σ(xa) ≤ σ(x) + 1. Figure 32.7 An illustration for the proof of Lemma 32.2. The figure shows that r ≤ σ(x) + 1, where r = σ(xa). Figure 32.8 An illustration for the proof of Lemma 32.3. The figure shows that r = σ(P[:q]a), where q = σ(x) and r = σ(xa). Proof Referring to Figure 32.7, let r = σ(xa). If r = 0, then the conclusion σ(xa) = r ≤ σ(x)+1 is trivially satisfied since σ(x) is

nonnegative. Now assume that r > 0. Then, P[:r] ⊐ xa, by the definition of σ. Thus, P[:r

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

原书定位详情

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

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

EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea