KMP算法 学习小记

发表于 | 分类于
KMP是一种字符串匹配算法，通过对模式字符串的处理，可以达到O(n+m)的时间复杂度

正文

参考文章字符串匹配的KMP算法

简易的匹配算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
对于字符串匹配，一种显而易见的想法是
[B]ABABCABCD
[A]BC
B[A]BABCABCD
 [A]BC
开始尝试匹配下一位
BA[B]ABCABCD
 A[B]C
BAB[A]BCABCD
 AB[C]
当检测到A,C不匹配
则退回到主串匹配开始的下一位重新匹配
BA[B]ABCABCD
  [A]BC
这一过程称为'回溯'
显然因为大量的回溯使得在最坏情况下时间复杂度达到了O(n*m)

KMP算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
对于形如下的匹配
BBC ABCDAB[ ]ABCDABCDABDE
    ABCDAB[D]
基于一种事实，即我们已经知道已经成功匹配的部分是 ABCDAB，那么在
BBC ABCDAB[ ]ABCDABCDABDE
        AB[C]DABD
之前的部分都是冗余的，KMP算法通过对子串的特殊处理直接跳转到这一步，避免了回溯。
构建一张表如下
ABCDABD
0000120
其中A=1代表若字符'A'已经匹配，则新的匹配可以从子串中序号为1的字符'B'(从0开始计数)重新开始。
B=2则表示由于'AB'已经匹配，子串开头的'AB'就不用再额外匹配了，即从'C'开始匹配。
对于这张表的使用解读如下
当匹配到
BBC ABCDAB[ ]ABCDABCDABDE
    ABCDAB[D]
因为前一个字符B=2，则可以直接跳转到
BBC ABCDAB[ ]ABCDABCDABDE
        AB[C]DABD

‘表’的计算

1
2
3
4
5
6
7
8
以'ABCD[A]BD'中的'A'为例
取出'ABCDA'
计算前缀字符串['A', 'AB', 'ABC', 'ABCD']
计算后缀字符串['BCDA', 'CDA', 'DA', 'A']
找出其中相同的字符串'A'
该字符串的长度为1
若结果有多个，取长度最大的

Demo

不想慢慢造轮子，就用python写了，能体现算法就好Orz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# -*- coding: utf-8 -*-
s = 'BBC ABCDAB ABCDABCDABDE'
t = 'ABCDABD'
def GetPat(s):
    r1 = [s[:i+1] for i in range(len(s)-1)]
    r2 = [s[i+1:] for i in range(len(s)-1)]
    return max([len(x) for x in r1 if x in r2] + [0])
def GetAllPat(s):
    return [GetPat(s[:i+1]) for i in range(len(s))]
def main(s, t):
    pat = GetAllPat(t)
    #print pat
    i = 0
    j = 0
    while i < len(s):
        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
                j += 1
                print i, j
            elif j == 0:
                i += 1
            else:
                j = pat[j-1]
        if i == len(s):
            print 'traverse end.'
            break
        else:
            j = 0
if __name__ == '__main__':
    main(s, t)

结语

ps: 感冒貌似快好了(一感冒真的除了躺着什么都不想做…)