数据结构和算法

Python中的字符串匹配算法分析

在Python在str对象的find、index、replace等操作都是基于字符串匹配的。通过阅读Python的源代码可知，在Python中的字符串匹配算法是基于Boyer-Moore、Horspool和Sunday的混合。

关于它的详细介绍可以访问这个网页： http://effbot.org/zone/stringlib.htm

用Python代码实现如下：

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
38
39
40
41
42
43
44
45
46
47
#!/usr/bin/env python
#-*- coding:utf-8 -*-


def make_delta1(p):
    ALPHABET_LEN = 256
    i = 0
    patternlen = len(p)
    delta1 = [0] * ALPHABET_LEN

    while i < ALPHABET_LEN:
        delta1[i] = patternlen
        i += 1

    i = 0
    while i < patternlen-1:
        delta1[ord(p[i])] = patternlen-1 - i
        i += 1
    return delta1


def find(s, p):
    # find first occurrence of p in s
    n = len(s)
    m = len(p)
    delta1 = make_delta1(p)
    skip = delta1[ord(p[m-1])]
    i = 0
    while i <= n-m:
        if s[i+m-1] == p[m-1]:  # (boyer-moore)
            # potential match
            if s[i:i+m-1] == p[:m-1]:
                return i
            if s[i+m] not in p:
                i = i + m + 1   # (sunday)
            else:
                i = i + skip    # (horspool)
        else:
            # skip
            if s[i+m] not in p:
                i = i + m + 1   # (sunday)
            else:
                i = i + 1
    return -1                   # not found

if __name__ == '__main__':
    print find("HERE IS A SILMPLE EXAMPLE", "EXAMPLE")