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