字符串匹配-bf-rk

发表于 | 分类于 | 阅读次数:
字数统计: 632 | 阅读时长 ≈ 3

主串 子串(模式串)

BF算法 在主串中检查起始位置分别是0、1、2…n-m且长度为m的n-m+1个子串

时间复杂度是n*m

但是在实际开发的过程中 是比较常用的

因为

大部分情况下 模式串和主串的长度都不会太长

而且每次模式串与主串中的子串匹配的时候 当中途遇到不能匹配的字符时 就停止了 不需要把字符串都比对一下 大部分情况下 够用

朴素字符串匹配算法思想简单 代码实现也非常简单 简单意味着不容易出错
在满足性能要求的前提下 简单是首选

RK

在朴素字符串匹配的基础上 引入哈希

对每个子串分别求哈希值 然后拿子串的哈希值与模式串的哈希值比较

理想情况下的时间复杂度是n

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#!/usr/bin/python
# -*- coding: UTF-8 -*-

from time import time


def bf(main, pattern):
    """
    字符串匹配，bf暴搜
    :param main: 主串
    :param pattern: 模式串
    :return:
    """
    n = len(main)
    m = len(pattern)

    if n <= m:
        return 0 if pattern == main else -1

    for i in range(n-m+1):
        for j in range(m):
            if main[i+j] == pattern[j]:
                if j == m-1:
                    return i
                else:
                    continue
            else:
                break
    return -1


def simple_hash(s, start, end):
    """
    计算子串的哈希值
    每个字符取acs-ii码后求和
    :param s:
    :param start:
    :param end:
    :return:
    """
    assert start <= end

    ret = 0
    for c in s[start: end+1]:
        ret += ord(c)
    return ret


def rk(main, pattern):
    n = len(main)
    m = len(pattern)

    if n <= m:
        return 0 if pattern == main else -1

    # 子串哈希值表
    hash_memo = [None] * (n-m+1)
    hash_memo[0] = simple_hash(main, 0, m-1)
    for i in range(1, n-m+1):
        hash_memo[i] = hash_memo[i-1] - simple_hash(main, i-1, i-1) + simple_hash(main, i+m-1, i+m-1)

    # 模式串哈希值
    hash_p = simple_hash(pattern, 0, m-1)

    for i, h in enumerate(hash_memo):
        # 可能存在哈希冲突
        if h == hash_p:
            if pattern == main[i:i+m]:
                return i
            else:
                continue
    return -1


if __name__ == '__main__':
    m_str = 'a'*10000
    p_str = 'a'*200+'b'

    print('--- time consume ---')
    t = time()
    print('[bf] result:', bf(m_str, p_str))
    print('[bf] time cost: {0:.5}s'.format(time()-t))

    t = time()
    print('[rk] result:', rk(m_str, p_str))
    print('[rk] time cost: {0:.5}s'.format(time()-t))

    print('')
    print('--- search ---')
    m_str = 'thequickbrownfoxjumpsoverthelazydog'
    p_str = 'jump'
    print('[bf] result:', bf(m_str, p_str))
    print('[rk] result:', rk(m_str, p_str))

输出如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
--- time consume ---
('[bf] result:', -1)
[bf] time cost: 0.27776s
('[rk] result:', -1)
[rk] time cost: 0.012524s

--- search ---
('[bf] result:', 16)
('[rk] result:', 16)

# 如上是普通cpython 2的输出

# 纯粹的py代码 可以使用pypy来加速

--- time consume ---
('[bf] result:', -1)
[bf] time cost: 0.033931s
('[rk] result:', -1)
[rk] time cost: 0.02212s

--- search ---
('[bf] result:', 16)
('[rk] result:', 16)