字符串匹配算法

字符串匹配:本身是指在一个字符串中找到另一个字符串,可以暴力的方式按照字符来进行匹配。优化匹配的效率的方向是:减少不成功的匹配次数,比如KMP、BM等优化策略都是如此,通过某种方式,或者某种规则来加速匹配过程。

BF算法(暴力算法)

普通模式的匹配算法:两个循环嵌套进行匹配,直到匹配成功。

Golang语法下可以截取字符串进行比较:

1
2
3
4
5
6
7
8
9
10
11
// Golang语法字符串截取优化
func MatchUseGo(str string, target string) int {
strArr := []rune(str)
targetArr := []rune(target)
for i := 0; i <= len(strArr)-len(targetArr); i++ {
if target == string(strArr[i:i+len(targetArr)]) {
return i
}
}
return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// BF算法:暴力算法
func MatchBF(str string, target string) int {
strArr := []rune(str)
targetArr := []rune(target)
for i := 0; i <= len(strArr)-len(targetArr); i++ {
match := true
if target == string(strArr[i:len(targetArr)]) {
return i
}
for j := 0; j < len(targetArr); j++ {
if strArr[i+j] != targetArr[j] {
match = false
break
}
}
if match {
return i
}
}
return -1
}

RK算法(基于BF算法的改进)

核心思想是哈希,即在详细比较之前,先使用hash进行比较,如果不匹配则右移。如果匹配,由于hash值可能存在碰撞的情况,因此需要进行详细判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// RK算法:使用hash匹配匹配进行优化
func MatchRK(str string, target string) int {
strArr := []rune(str)
targetArr := []rune(target)
for i := 0; i <= len(strArr)-len(targetArr); i++ {
// 使用字符串的hash进行匹配,如果一致再进行详细匹配
if md5.Sum([]byte(string(strArr[i:i+len(targetArr)]))) != md5.Sum([]byte(target)) {
continue
}
match := true
for j := 0; j < len(targetArr); j++ {
if strArr[i+j] != targetArr[j] {
match = false
break
}
}
if match {
return i
}
}
return -1
}

KMP算法

关键在于部分匹配表(RMT表):字符串起始位置到当前位置的字符串,“前缀”和“后缀”的最长的共有元素长度。

移动位数 = 已匹配的字符数 - 对应的部分匹配值

部分匹配表代表:模式串中某个位置匹配失败的时候,可以直接转到某个位置开始重新开始匹配。

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
// KMP算法:部分匹配表,在匹配失败时,可以跳过部分字符匹配
func MatchKMP(str string, target string) int {
strArr := []rune(str)
targetArr := []rune(target)

// 构建部分匹配表(RMT表)
targetRMT := make([]int, len(targetArr))
k := -1
targetRMT[0] = -1
for i := 0; i < len(targetRMT) - 1; {
if k == -1 || targetArr[i] == targetArr[k] {
i++
k++
targetRMT[i] = k
} else {
k = targetRMT[k]
}
}

// 匹配
i, j := 0, 0
for ; i < len(strArr) && j < len(targetArr); {
if j == -1 || strArr[i] == targetArr[j] {
i++
j++
} else {
j = targetRMT[j] // 当前位置的字符匹配失败,直接转移到模式串匹配表对应位置
}
}
if j >= len(targetArr) {
return i - len(targetArr)
}

return -1
}

BM算法

从后往前对模式串进行扫描与主串进行匹配的,使用两个启发策略。

坏字符算法:坏字符:字符串中的某个字符跟模式串的某个字符不匹配时,这个失配字符为坏
字符。

  1. 模式串中有对应的坏字符时,让模式串最靠右的对应字符与坏字符相对。
  2. 模式串中不存在坏字符,那么直接右移整个模式串长度这么大步数。

坏字符表的定义为:对于输入字符集合中的字符C,如果C不在模式串中,则C对应的值=模式串最末元素的索引值-字符C在模式串中最右出现的位置,字符不在模式串中时对应的值为-1。

好后缀算法

  1. 模式串中有子串和好后嘴完全匹配,则将最靠右的那个子串移动到好后缀的位置继续进行匹配。
  2. 如果不存在和好后缀完全匹配的子串,则好后缀中找到具有如下特征的最长子串,使得P[m-s...m] = P[0...s]
  3. 如果完全不存在和好后缀匹配的子串,则右移整个模式串。
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
func MatchBM(str string, target string) int {
strArr := []rune(str)
strLen := len(strArr)
targetArr := []rune(target)
targetLen := len(targetArr)

// 构建坏字符
badArr := make([]int, 256)
for i := 0; i < 256; i++ {
badArr[i] = targetLen
}
for i := 0; i < targetLen; i++ {
badArr[targetArr[i]] = targetLen - i - 1
}

// 构建好后缀
suff := make([]int, targetLen)
suff[targetLen-1] = targetLen
for i := targetLen - 2; i >= 0; i-- {
q := i
for q >= 0 && targetArr[q] == targetArr[targetLen-1-i+q] {
q = q - 1
}
suff[i] = i - q
}
goods := make([]int, targetLen)
for i := 0; i < targetLen; i++ {
goods[i] = targetLen
}
for i := targetLen - 1; i >= 0; i-- {
j := 0
if suff[i] == i+1 {
for ; j < targetLen-1-i; j++ {
if goods[j] == targetLen {
goods[j] = targetLen - 1 - i
}
}
}
}
for i := 0; i < targetLen-1; i++ {
goods[targetLen-1-suff[i]] = targetLen - 1 - i
}

// 查找
for i := 0; i <= strLen-targetLen; {
j := targetLen - 1
for ; j >= 0 && targetArr[j] == strArr[i+j]; j-- {
}
if j < 0 {
return i
}

max := badArr[int(strArr[i+j])] - targetLen + 1 + j
if goods[j] > max {
max = goods[j]
}

i = i + max
}
return -1
}

Sunday算法

从前往后扫描模式串的,其思路更像是对于“坏字符”策略的升华,关注的是主串中参与匹配的最末字符的下一位,将其与当前跳表判断下一步移动距离。

启发策略

  • 当遇到不匹配的字符时,如果关注的字符没有在模式串中出现则直接跳过即移动位数=子串长度+1
  • 当遇到不匹配的字符时,如果关注的字符在模式串中也存在时,其移动位数=模式串长度-该字符最右出现的位置(以0开始)或者移动位数=模式串中该子串最右出现的位置到尾部的距离+1
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
func MatchSunday(str string, target string) int {
strArr := []rune(str)
targetArr := []rune(target)
strLen := len(strArr)
targetLen := len(targetArr)

// 构建跳表
jump := make([]int, 255)
for i := 0; i < 255; i++ {
jump[i] = targetLen + 1
}
for i, c := range targetArr {
jump[c] = targetLen-i
}

for i := 0; i <= strLen-targetLen; {
flag := true
for j := 0; j < targetLen; j++ {
if targetArr[j] != strArr[i+j] {
flag = false
break
}
}
if flag {
return i
}

// 使用当前匹配对应长度的下一个字符计算移动距离
i = i + jump[strArr[i+targetLen]]
}

return -1
}