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