String Matching, Karp-Rabin

String Matching Problem

给定两个字符串 s 和 t,判断 s 是否是 t 的子串?如果是,出现在哪?出现了多少次?

Naive/Brute Force Algorithm

def match(s, t):
return any(s == t[i:i+len(s)] for i in range(len(t)-len(s))

子串比较的复杂度:O(s)O(|s|) ,因此算法时间复杂度为 O(s(ts))O(|s|*(|t|-|s|)) ,近似为 O(st)O(|s|*|t|)

Karp-Rabin Algorithm

Rolling Hash ADT

在 Naive Algorithm 中,我们每次比较子串的复杂度都是 O(s)O(|s|) ,但实际上,前后两次比较中,即 s==t[i:i+len(s)]s == t[i:i+len(s)]s==t[i+1:i+len(s)+1]s == t[i+1:i+len(s)+1] ,两个 t 的子串有 len(s)1len(s)-1 个字母是重复的,如果能够不用重复比较这些比较过的字母,就有可能将比较子串的复杂度将到 O(1)O(1)

于是 Rolling Hash ADT 诞生了:它维护一个字符串 x,同时提供以下三个方法

方法

功能

r()

r 就是 hash function,r() 返回当前子串的哈希值 h(x)

r.append(c)

将字母 c 放到 x 的末尾

r.skip(c)

将 x 的第一个字母移除

Karp-Rabin

def karp_r(s, t):
for c in s:
rs.append(c)
for c in t[:len(s)]:
rt.append(c)
if rs() == rt():
# compare char by char
pass
for i in range(len(s), len(t)):
rt.skip(t[i-len(s)])
rt.append(t[i])
if rs() == rt():
# compare char by char
pass

分析:

如果 Rolling Hash ADT 能够做到:

两个不同的子串的哈希值相等的概率 < 1s\frac{1}{|s|}

Karp-Rabin Algorithm 的算法复杂度就是:

O(s+ts1s)=O(s+t)O(|s| + |t|*|s|*\frac{1}{|s|}) = O(|s| + |t|)

An Rolling Hash Data Structure

想象 string x 是一个基数(base)为 a 的多位数(multi-digit number)u :

方法

基本实现

优化实现

r()

umodpu \bmod p ,其中 p 是接近 |s| 的随机质数,r 中保存着 u 和 x

umodpu \bmod p ,其中 p 是接近 |s| 的随机质数, r 中保存着 umodpu \bmod px|x| ,而并非 u

r.append(c)

u=ua+ord(c)u = u·a + ord(c)

(ua+ord(c))modp(u · a + ord(c))\bmod p[(umodp)a+ord(c)]modp[(u \bmod p)·a + ord(c)] \bmod p

r.skip(c)

u=ucax1u = u - c·a^{|x|-1}

[uord(c)(ax1modp)]modp[u - ord(c)·(a^{|x|-1} \bmod p)] \bmod p

[(umodp)ord(c)(ax1modp)]modp[(u \bmod p) - ord(c)·(a^{|x|-1} \bmod p)] \bmod p

在实际问题中 a 就是所有可能的字符数量。