字符串匹配算法

发表于 | 分类于 |
1,644 | 8

字符串匹配：本身是指在一个字符串中找到另一个字符串，可以暴力的方式按照字符来进行匹配。优化匹配的效率的方向是：减少不成功的匹配次数，比如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
}