字符搜索匹配算法 03 Rabin-Karp Fingerprint & 字符串哈希
Rabin-Karp Fingerprint Rabin-Karp fingerprint(RK) 基于 modular hashing： Compute a hash of pattern characters 0 to M - 1. For each i, compute a hash of text characters i to M + i - 1. If pattern hash = text substring hash, check for a match. 如果在一一比较中对text的每个子串都重新计算hash，那么速度比暴力算法还慢。 所以算法的关键在于如何高效地计算哈希值：Horner’s method - M阶多项式hash的线性时间方法 $$a^b \pmod c = (a \pmod c)^b$$ 引理： $$(a \times b) \pmod c = [( a \pmod c ) \times (b \pmod c) ] \pmod c$$...