字符串匹配

复试的时候一个KMP卡半天都没写出来,太眼高手低了吧……

Robin-Karp

预处理时间 , 最坏运行时间

Robin-Karp算法其实感觉和直接比较的方式很相近,只是对于比较的过程进行了优化,通过模运算,或者哈希等方式,尽可能将比较的复杂度从 降到 ,但是这样就会带来伪命中点,所以最坏情况会和直接比较的复杂度相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
RABIN-KARP-MATCHER(T,P,d,q):
n = T.length
m = P.length
h = d^(m-1) mod q
p = 0
t_0 = 0
// p过大的时候通过模运算来减少比较所需复杂度
for i = 1 to m
p = (dp + p[i]) mod q
t_0 = (dt_0 + T[i]) mod q
for s = 0 to n-m
// 余数一样就实际比较一下避免伪命中点
if p == t_s
if P[1..m] = T[s+1..s+m]
print"yes we get s"
// 没中就移位
if s < n-m
t_(s+1) = (d(t_s - T[s+1]h) + T[s+m+1]) mod q

霍纳法则(Horner Rule)

秦九韶算法……

二维匹配

当匹配扩展到二维是,即在一个 的二维字符组成中搜寻一个给定的 的模式。
同样的思想,首先对模式矩阵进行处理,对每一列都进行哈希然后进行组合,就将二维降维成了一维的字符串,如果每列得到k个字符,则一共是 个字符组成的字符串。
然后,对大矩阵的前 行进行同样的操作,用同样的方法能得到一个长度为的串。
对接下来的 行进行相同的操作直至找到相同模式,这样就二维降维成了一维,并且能够使用一些trick来提高效率。
类似一维的情况,这里每次匹配时,转化后的一维串可以通过上次的串直接计算出来。(类似于Rabin-Karp由 可以在常数时间内计算出

有限自动机

预处理时间 , 最坏运行时间

在学过编译原理后就能感觉到这种方式其实和编译器中的DFA干的是一件事。通过待匹配的模式串建立一个有限状态自动机来接收输入并判断是否接受。

Knuth-Morris-Pratt

预处理时间 , 最坏运行时间

KMP算法的核心就是通过计算模式串本身所携带的信息来得到每次比较失败后应该移动的距离,也就是前缀函数的功能。

1
2


Boyer-Moore

预处理时间 , 最好运行时间 , 最坏运行时间

AC自动机

Reference

《算法导论》
《算法》(R.Sedgewick & K.Wayne)
http://blog.sina.com.cn/s/blog_6a09b5a70100nhnr.html