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

Dear 丶 2023-06-30 15:54 7阅读 0赞

# \[数据结构与算法\] 字符串的匹配算法（KMP算法） #

标签： `实现strStr` `KMP算法`

--------------------

上一篇文章概述了一下BF算法以及缺点，这篇文章来说明一下KMP算法，对BF算法的优化。

如果你还不知道BF算法是什么： [点击我][Link 1] 先了解匹配字符串的暴力匹配法，然后再看KMP，感觉会更清晰一点。

## KMP算法 ##

这个算法，是对BF算法的一个优化，为什么说优化呢，KMP算法当两个字符不相等的时候，i不需要回溯，只需要j回溯，j回溯到什么位置呢？先不看这个问题，先看kmp算法的例子。

假设给定的str是`a b a b c a a b c a c b c b`  
给定的pattern是`a b c a c`

推导过程手写了一份：

第一步：

`i`指向当前`str`的索引，`j`指向`pattern`的索引，从0开始相等，然后`i++,j++`。当`i==2 j==2`遇到不相等的情况：  
![kmp-01][]

第二步：  
![kmp-02][]  
第三步：

![kmp-03][]

为什么会是这样：

![kmp-04][]  
![kmp-05][]

总结，实际上最大前后缀，咱们可以细细想一下上面的例子。

此时str 是`a b c x y z a b c x y z a b c d c d`  
pattern是 `a b c x y z a b c d`

比较到最后一个字符 x 和 d是不等的。这时候说明，`pattern`中字符`d`以前 的字符已经完全和str中的 `x`字符以前的字符完全匹配。这时候我们只需要关注pattern中j的位置的变化，也就是求`d`字符的索引j的下一个位置，也就是next表，也即使说这个`d`字符对应的j要移动到的位置的关系表。 `d`为`j`的索引，如果和对应 的`i`值不相等，那么应该跳回到`j`以前的字符的最大公共前缀，也就是next表中的 next\[j\]的值。

BF算法是这样：

const strStr = (str, pattern) =>  { 
    		let i = 0, j = 0
    		while (i < str.length && j < pattern.length ) { 
    			if (str[i] == pattern[j]) { 
    				i++
    				j++
    			} else { 
    				i = i - j + 1 // 回溯到当前比较的起点的下一个位置
    				j = 0
    			}
    		}
    		if (j == pattern.length) return i - j
    		return -1
    	}

利用KMP算法的话，i 不需要变化，j回溯，代码会是下面这样：

const strStr = (str, pattern) =>  { 
    		let i = 0, j = 0
    		while (i < str.length && j < pattern.length ) { 
    			if (str[i] == pattern[j] || j == -1) {  
    			// 为什么j==-1为判定条件之一，先忽略，往后面看
    				i++
    				j++
    			} else { 
    				// 优化之前
    				// i = i - j + 1 // 回溯到当前比较的起点的下一个位置
    				// j = 0
    				
    				// 优化之后 
    				j = next[j] // next表存储着这个位置的下个回溯位置
    			}
    		}
    		if (j == pattern.length) return i - j
    		return -1
    	}

那么问题来了，怎么求这个next表，也就是对应j位置的下一个回溯位置，代码如下：

let next =  getPrefixTable(pattern)

好的我知道你肯定一脸懵逼，这个推导过程while循环内的，if语句判定相等的过程是容易理解的，不相等的情况有点迷糊，直接看这个[油管up主黄浩杰的讲解][up] ，楼主也是看了很多视频和文章，感觉就这个最容易理解点。

资料：

[王卓老师-KMP算法][-KMP]  
[油管up主黄浩杰的讲解][up]

王卓老师的讲解bp算法是好理解，KMP的算法原理也好理解【很关键，知道怎么跳过无意义的比较】，但是next表也就是j回溯位置的数组求解就有点懵，而且王老师计算是索引1开始，数组一般是0开始，需要转换一下。

建议先看王老师的原理，然后看油管黄浩杰的 next表的求解原理。

[Link 1]: https://blog.csdn.net/a5534789/article/details/104030856
[kmp-01]: https://img-blog.csdnimg.cn/20200118150700951.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5,size_16,color_FFFFFF,t_70
[kmp-02]: https://img-blog.csdnimg.cn/20200118151015746.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5,size_16,color_FFFFFF,t_70
[kmp-03]: https://img-blog.csdnimg.cn/2020011815152260.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5,size_16,color_FFFFFF,t_70
[kmp-04]: https://img-blog.csdnimg.cn/20200118151611586.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5,size_16,color_FFFFFF,t_70
[kmp-05]: https://img-blog.csdnimg.cn/20200118153359410.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5,size_16,color_FFFFFF,t_70
[up]: https://www.youtube.com/watch?v=dgPabAsTFa8&pbjreload=10
[-KMP]: https://www.bilibili.com/video/av34404827