open-courses
Search…
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 p
x|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 就是所有可能的字符数量。