KMP算法

在字符串匹配算法里面有一种算法叫kmp算法。其实这种算法原理很简单，用模式串的前缀和后缀性质减少比较次数，从而达到提高效率的目的。不可否认的是，字符串匹配场景还是很常见的。
假如在字符串 T = {a,b,c,d,e,a,b,c,d,a,b,d} 中搜索字符串 P = {a,b,c,d,a,b,d}，则字符串 P 成为模式串。

其实KMP算法建立在 3 条引理之上的。见算法导论（p591）。也可以参考知乎更好的理解和掌握 KMP 算法?

直接贴代码..

//Go语言版，用Go语言实现只是为了学习Go的语法，所以代码风格不太统一，例如切片的声明方式。
func cateMaxLens(pat string) []int  {
	plen := len(pat)
	maxMatchLenArys := make([]int, plen)   // 声明切片
	maxlen := 0

	// 当i=k时，计算i=0开始，和i=k开始，最常公共字符串
	for i:=1; i<plen; i++ {
		for maxlen > 0 && pat[maxlen] != pat[i] {
			maxlen = maxMatchLenArys[maxlen-1]
		}
		if pat[i] == pat[maxlen] {
			maxlen++
		}
		maxMatchLenArys[i] = maxlen
	}
	return maxMatchLenArys
}

func kmp(src string, pat string) []int {
	var posArys []int
	maxMatchLenArys := cateMaxLens(pat)
	count := 0
	for i:=0; i< len(src); i++ {
		for count>0 && pat[count] != src[i] {
			count = maxMatchLenArys[count-1] // 为了确定在前缀和后缀含有公共子串的前提下，下次匹配时的起始位置
		}
		if pat[count] == src[i]{
			count++
		}
		if count == len(pat) {
			posArys = append(posArys, i-len(pat) + 1)
			count = maxMatchLenArys[count-1]
		}
	}

	return posArys // posArys记录匹配到的字符串的所有起始位置，例如src="ababa",pat="abab",则posArys[0,2]，如果没有匹配到，则posArys=[]
}