KMP算法理解

KMP简介

KMP优于暴力匹配算法的核心是它利用了模式串本身对称（非中心对称）的特性，基于这个特性当在遇到字符失配时跳过一部分字符以达到提升查找速度的目的。这个特性是什么呢，就是字符串的前缀集合与后缀集合交集中最长字符的长度，专业术语叫部分匹配表(Partial Match Table)，程序中通常命名它为next数组。

理解了部分匹配表的含意再来看KMP的查找过就没那么难了，难点我觉得在部分匹配表(next数组)的求解过程，但是网上的文章大多不是一笔带过就是各种数学公式推导，数学不好的我读起来真烧脑，始终理解不了，直到看了这篇：KMP算法中如何计算next数组 才茅塞顿开，借助找对称的方式一下子就了然了，致敬。

next数组求解过程

假设模式串为：agctagcagctagct，根据定义我们可以口算出next数组的值为[0,0,0,0,1,2,3,1,2,3,4,5,6,7,4]，即模式串的前i+1个字符的前缀和后缀的最长公共序列的长度为next[i]。

上边的next数组是我们人肉计算得出来的，那么用程序如何求解呢？

原理就是利用next[0]~next[i]来求解next[i+1]。

为什么已知next[0]~next[i]就能得出next[i+1]呢？

a：next[0]=0，

ag：pattern[1]=g，pattern[0]=a，不相等，所以next[1]=0，

agc：pattern[2]=c，pattern[0]=a，不相等，所以next[2]=0，

agct：pattern[3]=t，pattern[0]=a，不相等，所以next[3]=0，

agcta：pattern[4]=a，pattern[0]=a，相等，所以next[4]=1，

agctag：pattern[5]=g，pattern[1]=g，相等，所以next[5]=2，

agctagc：pattern[6]=c，pattern[2]=c，相等，所以next[6]=3，

…… agctagcagctagc：pattern[13]=c，pattern[6]=c，相等，所以next[13]=7

1023733-4ac9f00ab22c774b

问题来了

agctagcagctagct：pattern[14]=t，pattern[7]=a，不相等。

怎么办？于是next[14]=0吗？很显然agct才是前缀和后缀的最长共同序列，next[14]=4。

1023733-f6ae7050fe449aef

怎样找到agct呢？

原理就是找次长公共序列。

图中橙色的A表示已经确定的最长公共序列，绿色的T将要与开头的A后面的元素进行比较，如果比对失败，我们需要寻找次长公共序列B，然后T再与开头的B后面元素进行比对。

为什么要找次长公共序列呢？

1023733-d61d68f1230f8144

从上图橙色块都是一样的，假如存在次长公共序列，第二幅图表明橙色块必然同时以B开头且以B结尾即，第三幅图所示，这就得出T位置的次长公共序列长度就是橙色块A的最长公共序列长度。

因此，计算agctagcagctagc的次长公共序列就是要计算A=agctagc的最长公共序列，而这个已经计算过了，next[6]=3，得到agc。

通过图，借助找对称也就理解了next数组的求解原理。

Golang实践算法

 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88


package main

import "fmt"

//求最大前缀
func computePrefix(pattern string) []int{
	pLen := len(pattern)
	//切片用来存放最计算结果
	maxPrefix:=make([]int,pLen)

	//前缀末尾位置，即最大前缀长度
	end:=0
	maxPrefix[0] = 0

	//错开一位从索引1开始遍历整个模式串
	for i:=1; i< pLen; i++{
		//如果相同就保存结果，前缀末尾指针往前走，继续下一个字符匹配
		if pattern[i]==pattern[end]{
			maxPrefix[i]=end+1
			end++
			continue
		}
		//失配时使用次长公共序列或更短的公共序列来比对
		for end > 0{
			//注意是end-1不是i-1,即使用次长公共序列，失配就回溯直到end归零，即回来起点
			end=maxPrefix[end-1]
			if pattern[i] == pattern[end]{
				maxPrefix[i] = end+1
				end++
				break
			}
		}
		if end ==0 {
			maxPrefix[i]=0
		}
	}
	return maxPrefix
}

func KMP(target,pattern string) int {
	tLen :=len(target)
	pLen := len(pattern)
	next := computePrefix(pattern)

	//模式串的位置
	k := 0

	// 遍历整个目标串
	for i:=0; i< tLen; i++ {
		for k > 0 && pattern[k] != target[i] {
			//失配时跳转过程
			//      ->i<-  <- i
			//...ABCABE... <- target
			//   ABCABD    <- pattern
			//   012345    <- k
			//     ->4<-   <- k-1
			//------------------------------分割线
			//      ->i<-  <- i
			//...ABCABE... <- target
			//   ABCABD    <- pattern
			//   012345    <- k
			//    >2<-     <- next[k-1]
			//E和C比较
			k = next[k-1]
		}
		if pattern[k] == target[i] {
			k = k +1
		}
		// k已经到达模式串的结尾，即已找到匹配
		//为什么要减1，因为上边k已加1
		if k -1 == pLen -1  {
			return i-pLen+1
		}
	}
    // 未找到
	return  -1
}


func main()  {
	pattern := "ABCDABD"
	target := "BBC ABCDAB ABCDABCDABDE"
	next:=computePrefix(pattern)
	p :=KMP(target,pattern)
	fmt.Println(next)
	fmt.Println(p)

}