字符串匹配算法

发表于 | 更新于

做leetcode做到了一道实现strStr()函数的题,实际上就是字符串匹配算法,令我不由得联想到了鼎鼎有名的KMP算法.随后在网上又搜到了比KMP还快,还简单的算法,what???啊饶了我吧orz

Brute Force算法

暴力算法…我就是用这种算法过leetcode的,毕竟没时间要求

简而言之,就是字符串与模式串中的字符一个个匹配,如果不匹配,则字符串字符进一位,模式串从头匹配.果然Brute Force!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func strStr(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}
loop:
	for i := 0; i < len(haystack)-len(needle)+1; i++ {
		for j := 0; j < len(needle); j++ {
			if haystack[i+j] != needle[j] {
				continue loop
			}
		}
		return i
	}
	return -1
}

KMP算法

之前觉得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
34
35
36
37
38
func kmpSearch(str, subStr string) int {
	nextArray := getNext(subStr)
	i, j := 0, 0
	for i < len(str) && j < len(subStr) {
		if j == -1 || str[i] == subStr[j] {
			i++
			j++
		} else {
			j = nextArray[j]
		}
	}
	if j == len(subStr) {
		return i - j
	}
	return -1
}

//calculate the next array
func getNext(s string) []int {
	next := make([]int, len(s))
	next[0] = -1
	k := -1
	j := 0
	for j < len(s)-1 {
		if k == -1 || s[j] == s[k] {
			k++
			j++
			if s[j] == s[k] {
				next[j] = next[k]
			} else {
				next[j] = k
			}
		} else {
			k = next[k]
		}
	}
	return next
}

暴力法每次匹配失败后都要重头开始,之前匹配成功的结果被白白浪费很可惜,那么试想一下我们该怎样利用之前已匹配成功的资源?这就是KMP算法的核心

KMP算法采用了一个next数组,这个数组由模式串计算而来,是模式串的最长公用前后缀表.听起来有些复杂,举个例子:

1
2
模式串:      A B C D A B D
对应数组:    0 0 0 0 1 2 0

那么这个next数组是怎么产生的呢?我们现在看看A,由于只有一个字符,它的最长前缀为””,最长后缀为””,最长公用前后缀的长度为0

接下来是AB,它的最长公用前后缀为””,因此也是0

以此类推…:

字符串 最长公用前后缀 长度
A 0
AB 0
ABC 0
ABCD 0
ABCDA A 1
ABCDAB AB 2
ABCDABD 0

字符串匹配时有了这样的一个数组,就可以简化算法复杂度

为什么呢?当模式串不匹配时,如果那个不匹配的字符前面的后缀子串有着相同的前缀子串的话,那么直接将模式串移至前缀子串的位置就可以大大缩减匹配时间,next数组记录的值实际上就是模式串需要移至的值

Sunday算法

Sunday算法是由BM算法改进而来,BM算法是另一个模式匹配算法,暂时不议

Sunday算法是从前往后匹配,在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符:

  • 如果该字符没有在模式串中出现则直接跳过,即移动位数=模式串长度+1
  • 否则,其移动位数=模式串长度-该字符最右出现的位置(以0开始)=模式串中该字符最右出现的位置到尾部的距离+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
main string: substring searching
              ^    ^
              | u和e不符,又模式串中没有i,主串字符跳至i后一位
              v
sub string:  search


main string: substring searching
                    ^     ^
                    | n和s不符,模式串中有r,将主串和模式串中的最右边的r对齐
                    v
sub string:         search


main string: substring searching
                       ^  ^
                       | 从头开始匹配,匹配成功
                       v  v
sub string:            search

使用Sunday算法,仅仅匹配错误了两次就成功了,由此可见其高效性

下面是实现的代码:

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
func sundaySearch(str, subStr string) int {
	subMap := make(map[byte]int)
	for i := 0; i < len(subStr); i++ {
		subMap[subStr[i]] = i
	}

	i, j := 0, 0
	for i < len(str) && j < len(subStr) {
		if str[i] == subStr[j] {
			i++
			j++
		} else {
			shift := 0
			if ind, ok := subMap[str[i-j+len(subStr)]]; !ok {
				shift = -1
			} else {
				shift = ind
			}
			i = i - shift + len(subStr)
			j = 0
		}

	}
	if j == len(subStr) {
		return i - j
	}
	return -1
}

用字典存储模式串的值过于消耗空间,由于这里字符就是字节,因此可以用大小为256的数组代替:

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
func sundaySearch(str, subStr string) int {
	subArray := [256]int{}
	for i := 0; i < 256; i++ {
		subArray[i] = len(subStr) + 1
	}
	for i := 0; i < len(subStr); i++ {
		subArray[subStr[i]] = len(subStr) - i
	}

	i, j := 0, 0
	for i < len(str) && j < len(subStr) {
		if str[i] == subStr[j] {
			i++
			j++
		} else {
			i += subArray[str[i-j+len(subStr)]] - j
			j = 0
		}

	}
	if j == len(subStr) {
		return i - j
	}
	return -1
}

小结

字符串匹配算法有很多种,这里仅仅是列出了比较具有代表性的几种…另外,Sunday算法真的是速度又快有简单,以后谁再跟我提KMP我跟谁急

参考文档

阮一峰的网络日志:字符串匹配的KMP算法

Chris的灌水乐园:从头到尾彻底理解KMP

一个人的天空:字符串匹配算法总结(转)

Switch_vov:字符串匹配——Sunday算法

0%