更多优质内容
请关注公众号

算法小白的入门日记(二六)高效字符串匹配算法——KMP算法-张柏沛IT博客

正文内容

算法小白的入门日记(二六)高效字符串匹配算法——KMP算法

栏目:算法专题 系列:算法小白的入门日记 发布时间:2022-01-24 22:59 浏览量:1221
本系列文章目录
展开/收起

· KMP算法思路

KMP算法也是通过减少字符串匹配的轮数进行优化的,BM算法关注“坏字符”和“好后缀”,KMP算法关注“已匹配的前缀”。

KMP算法的思路是:将主串A的子串与模式串B进行多轮匹配,每轮匹配中从前往后比对字符,需要将AB的已匹配串中的相同B前缀串和A后缀串对齐,从而跳过若干轮匹配。


具体步骤:

1、把主串和模式串的首位对齐,从前到后对逐个字符进行比较,得到第一个坏字符,坏字符之前的内容就是已匹配前缀,已匹配前缀是 “GTGTG”。


2、需要从已匹配前缀中找到A的最长可匹配后缀子串B的最长可匹配前缀子串(下面简称为 匹配前缀 和 匹配后缀),即GTG,将他们对齐。




3、重复上述过程,确定新的已匹配前缀GTG,和它的匹配后缀与匹配前缀,即G,并对齐:


然后继续从对齐的位置往后进行字符比较。由于 "T" != “A”,因此 “A”是个坏字符,已匹配前缀串G是个单字符的字符串,没有匹配前缀和后缀。


4、如果没有已匹配前缀(即第一个字符就不匹配)则模式串B只往后移动一位;如果已匹配前缀串中没有相同的匹配前缀和匹配后缀,则模式串B往后移动已匹配前缀串的位数。


重复上述过程。


什么是最长可匹配后缀(子串)和最长可匹配前缀(子串)?如果一个字符串x,x的后缀子串y也是它的前缀子串z,而且x和z本身≠y,那么这个子串x就是最长可匹配前缀子串同时也是最长可匹配后缀子串。

例如 ABCA 的最长可匹配前缀为"A",ABCAB 的最长可匹配前缀为"AB"。GTGTG的最长可匹配前缀是“GTG”。



· KMP预处理

KMP算法的关键是预处理得到模式串B所有 前缀子串 的匹配前缀和匹配后缀

本例中的模式串B是 “GTGTGCF”,它所有的前缀子串 B[:i] 包括

“”,“G”,“GT”,“GTG”,“GTGT”,“GTGTG”,“GTGTGC”,“GTGTGCF”。因此一个长度是 n 的字符串,它的已匹配子串的个数为n+1。

举个例子:模式串B(“GTGTGCF”)的一个前缀子串 “GTGT”,它的匹配前缀是 “GT”。

匹配前缀和后缀只和模式串B自己有关,和主串无关。


预处理过程如下:

构建一个next数组,next[i]表示B中长度为 i 的前缀子串的可匹配前缀串的后一个字符的下标(i∈[1, len(B)]),B[:i]表示长度为 i 的前缀子串。

B[:next[i]]就是B[:i]的最长可匹配前缀串。

例如:GTGTGCF的一个已匹配子串GTGTG,i=5,它的最长可匹配前缀"GTG"的下一个字符是"T",所以 next[5] = 3。


next数组的构建是一个动态规划的过程,next[i]依赖于next[j](k<i)。

假设有一个字符串 M,有两种情况:

如果 M 的最后一个字符b1 等于 M[:len(M)-1]这个字符串的匹配前缀的下一个字符b2。则M的匹配前缀就是M[:len(M)-1]的匹配前缀串+b2。否则 M[:len(M)-1]的匹配前缀的下一个字符b2 要回溯到M[:len(M)-2]的匹配前缀的下一个字符b3,判断b1和b3是否相同。


举个例子,已知 M = "GTGG",求next[4] = ?

M = "GTGG",M[:len(M)-1] = "GTG",M的最后一个字符是"G",M[:len(M)-1]的匹配前缀是M[0]这个"G",它的下一个字符是M[1] = "T"

"G" != "T" => 回溯 => M[:len(M)-2] = "GT", M[:len(M)-2]的匹配前缀是空字符串,它的下一个字符是M[0] = "G"

"G" == "G",所以 M的匹配前缀是“G”,它的下一个字符"T"。因此next[4] =1


写为公式就是:

欲求next[i],先得到 j = next[i-1]

1、如果 B[i-1] == B[j],则next[i] = j+1;

2、如果B[i-1] != B[j],则 j = next[i-2](回溯)并循环判断B[i-1] != B[j],如果判断成功则 。


​​​​​​​

如果B的长度为n,则next的大小也为n,即next只记录B的前n-1个长度的解,不记录B本身的解,因为如果前缀子串就是B本身,那么本轮匹配已经成功,无需再找其匹配前缀。


下面是KMP算法:

func KMP(a, b string) int{
	if len(b) > len(a){
		return -1
	}

	next := _getNexts(b)	// 生成next数组
	start := 0 				// start是主串中要和模式串匹配的子串的首字符位置
	des := len(a) - len(b)
	j := 0		// j是本轮匹配中已匹配字符的下一个字符下标

	for start <= des{ 
		for i:=j; i<len(b); i++{
			if b[i] != a[start + i]{	// 如果匹配到坏字符时,已匹配字符个数大于0,则将b后移若干位使得a中的坏字符位置和b的最长匹配前缀的下一个字符位置对齐
				if j != 0{
					start = start + (i - next[i])		// 代码的直接意思是将a中的坏字符位置和b的最长匹配前缀的下一个字符位置对其(等价于将 b中的最长匹配前缀和a中的最长匹配后缀对其)
				}else{	// 如果匹配到坏字符时,已匹配字符个数为0,则b往后移一位
					start++
				}
				j = next[i]
				break
			}else{
				j++
			}
		}
		if j == len(b){		// 说明整个模式串b所有字符都比对成功
			return start
		}
	}
	return -1
}

func _getNexts(b string) []int{
	next := make([]int, len(b))
	next[0], next[1] = 0, 0
	j := 0

	for i:=2; i<len(b);i++{
		for j > 0 && b[i-1] != b[j]{
			j = next[j]		// j回溯到上一个匹配前缀(的下一个字符位置)
		}

		// 走到这里有两种情况,一是 b[i-1] == b[j], 一是j == 0 但还不知道是否 b[i-1] == b[j],因此需要判断一下 b[i-1] 是否等于 b[j]
		if b[i-1] == b[j]{
			j++
		}
		next[i] = j
	}
	return next
}

KMP的平均时间复杂度为O(m+n),空间复杂度O(m),m是模式串长度。




更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(二六)高效字符串匹配算法——KMP算法

热门推荐
推荐新闻