数据结构与算法-字符串匹配-KMP算法

Posted on | Edited on | In ,

时间复杂度是O(m+n),n是模式串长度、m是主串长度。空间复杂度O(n)，因为失效函数借助了一个数组长度为n

重点

  1. 比较的移动借鉴了BM算法，采用好前缀规则如图，遇到坏字符时候，假设好前缀的最长可匹配前缀子串长度为v,则模式串一次性移动j-v个距离，相当于将j变为v
  2. 求解失效数组

avator

匹配代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func KMP(str string, ptr string) int {
	next := getNext(ptr)
	i := 0
	j := 0
	for i < len(str) && j < len(ptr) {
		//如果匹配继续
		if j < 0 || str[i] == ptr[j] {
			j++
			i++
		} else {
			//发现badecode，滑动模式串，next[j]个位置，如果是0发现不等，会到-1,然后i移动，j移动
			j = next[j]
		}
	}

	if j == len(ptr) {
		return i - j
	}

	return -1
}

求解next数组代码

规律如下，假设模式串为a,那么遵循如下俩条规律

  1. 当a[0,i-1]的最长可匹配前子串是a[0,k-1]，的下一个字符a[i]等于a[k]，那么a[0,i]的最长匹配前缀就是a[0,k]
  2. 当a[i]不等于a[k]，我们要找到a[0,i-1]的次长匹配子串a[0,k’]，当a[k’+1]等于a[i]，那么a[0,k’]就是a[0,i]的最长匹配前缀
    1. 其中，a[0,k’]一定包含a[0,k-1]中，即next数组中，如图

avator

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

//失效函数,求解ptr的next数组，我们可以看做是ptr字符串和自己的最长前缀的匹配
//重点：
// 1、公式1：如果p[i]的最长匹配前缀子串是j,如果p[i+1]==p[j+1]，那么p[i+1]的最长匹配子串是j+1，next[i+1]=j+1
// 2、公式2：上述情况下如果p[i+1]!=p[j+1],我们认为j+1是坏字符串，应该将最长前缀字符串(在这里是模式串)挪动next[j+1]个距离假设是y，在继续查找，如果这时候p[i+1]==p[y],那么p[i+1]的最长匹配子串就是next[i+1]=y
func getNext(ptr string) []int {
	next := make([]int, len(ptr))
	next[0] = -1 //如果前缀只有一个字符是没有好前缀的

	i := 0
	j := -1

	//遍历模式串ptr
	for i < len(ptr)-1 {
		//j==-1时候，匹配失效，复位j=0说明没有匹配得上的最长前缀子串；
		// 如果ptr[i]==ptr[j],说明next[i]=j，然后俩个都++如果继续相等next[i+1]=j+1，
		if j == -1 || ptr[i] == ptr[j] {
			j++
			i++
			next[i] = j
		} else {
			//如果ptr[i] != ptr[j]并且j!=-1，相当于模式串的最长后缀和模式串的最长前缀无法匹配
			//这时候要移动j,移动的方案是假设j是坏字符，那么查找ptr[0,j]的最长前缀子串一定在next数组中（上面的分支已经匹配过了）
			//所以移动j，距离是next[j]（刚才匹配的最长前缀的长度）
			j = next[j] //****不会空指针的原因在上面的分支，上一次循环next[i++]=j++，i本身就>j，所以next[j]之前已经计算过了。一定是有值的
		}
	}
	fmt.Print(next)
	return next
}