【经典问题】字符串匹配

1、BF算法

BF(Brute Force)算法就是朴素的暴力匹配。BF算法的基本思想是从主串的start位置开始与模式串进行匹配,如果相等,则继续比较后续字符,如果不相等则模式串回溯到开始位置,主串回溯到start+1位置,继续进行比较直至模式串的所有字符都已比较成功,则匹配成功,或者主串所有的字符已经比较完毕,没有找到完全匹配的子串,则匹配失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def BF(s, p):
'''
Brute-Force算法实现字符串匹配
'''
indies = []
n = len(s)
m = len(p)
for i in range(n - m + 1):
index = i
for j in range(m):
if s[index] == p[j]:
index += 1
else:
break
if index - i == m:
indies.append(i)

return indies

print(BF('abcxabcdabcdabcy','abcdabcy'))

2、KMP算法

KMP(Knuth-Morris-Pratt)算法是对BF算法的改进,差别在于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
25
26
27
28
29
30
31
32
33
def getNextList(s):
n = len(s)
nextList = [0, 0]
j = 0
for i in range(1, n):
while j > 0 and s[i] != s[j]:
j = nextList[j]
if s[i] == s[j]:
j += 1
nextList.append(j)
return nextList

def KMP(s, p):
'''
Knuth-Morris-Pratt算法实现字符串匹配
'''
n = len(s)
m = len(p)
nextList = getNextList(p)
indies = []
j = 0
for i in range(n):
while s[i] != p[j] and j > 0:
j = nextList[j]

if s[i] == p[j]:
j += 1
if j == m:
indies.append(i-m+1)
j = nextList[j]
return indies

print(KMP('abcxabcdabcdabcy','abcdabcy'))

3、BM算法

BM(Boyer-Moore)算法是对KMP进一步的改进。总体来说BM算法效率是高于KMP算法的,文本量越大BM算法的效果越明显。BM算法通过两张表来改进移动的距离。

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
def getBMBC(pattern):
# 预生成坏字符表
BMBC = dict()
for i in range(len(pattern) - 1):
char = pattern[i]
# 记录坏字符最右位置(不包括模式串最右侧字符)
BMBC[char] = i + 1
return BMBC

def getBMGS(pattern):
# 预生成好后缀表
BMGS = dict()

# 无后缀仅根据坏字移位符规则
BMGS[''] = 0

for i in range(len(pattern)):

# 好后缀
GS = pattern[len(pattern) - i - 1:]

for j in range(len(pattern) - i - 1):

# 匹配部分
NGS = pattern[j:j + i + 1]

# 记录模式串中好后缀最靠右位置(除结尾处)
if GS == NGS:
BMGS[GS] = len(pattern) - j - i - 1
return BMGS

def BM(string, pattern):
'''
Boyer-Moore算法实现字符串查找
'''
m = len(pattern)
n = len(string)
i = 0
j = m
indies = []
BMBC = getBMBC(pattern=pattern) # 坏字符表
BMGS = getBMGS(pattern=pattern) # 好后缀表
while i < n:
while (j > 0):
if i + j -1 >= n: # 当无法继续向下搜索就返回值
return indies

# 主串判断匹配部分
a = string[i + j - 1:i + m]

# 模式串判断匹配部分
b = pattern[j - 1:]

# 当前位匹配成功则继续匹配
if a == b:
j = j - 1

# 当前位匹配失败根据规则移位
else:
i = i + max(BMGS.setdefault(b[1:], m), j - BMBC.setdefault(string[i + j - 1], 0))
j = m

# 匹配成功返回匹配位置
if j == 0:
indies.append(i)
i += 1
j = len(pattern)

print(BM('abcxabcdabcdabcy','abcdabcy'))
0%