原书出处
Introduction to Algorithms, Fourth Edition
32 第32章 字符串匹配
of ts+1 mod q from the value of ts mod q in constant time using equation (32.2) directly.
RABIN-KARP-MATCHER takes Θ(m) preprocessing time, and its matching time is Θ((n − m + 1)m) in the worst case, since (like the naive string-matching algorithm) the Rabin-Karp algorithm explicitly verifies every valid shift. If P = am and T = an, then verifying takes Θ((n−m+1)m) time, since each of the n−m+1 possible shifts is valid. In many applications, you expect few valid shifts—perhaps some
constant c of them. In such applications, the expected matching time of the algorithm is
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter032.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea