算法：字符串匹配算法：KMP算法

小鱼儿 2023-07-10 08:45 69阅读 0赞

字符串匹配算法  
暴力算法BF算法，利用哈希值进行比较的RK算法，以及尽量减少比较次数的BM算法  
![在这里插入图片描述][20200301172159346.png]  
![在这里插入图片描述][20200301172225844.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20200301172501878.png]

![在这里插入图片描述][20200301172528525.png]  
![在这里插入图片描述][20200301172546542.png]

next 数组

next数组到底是个什么鬼呢？这是一个一维整型数组，数组的下标代表了“已匹配前缀的下一个位置”，元素的值则是“最长可匹配前缀子串的下一个位置”。

或许这样的描述有些晦涩，我们来看一下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 3]  
当模式串的第一个字符就和主串不匹配时，并不存在已匹配前缀子串，更不存在最长可匹配前缀子串。这种情况对应的next数组下标是0，next\[0\]的元素值也是0。

如果已匹配前缀是G、GT、GTGTGC，并不存在最长可匹配前缀子串，所以对应的next数组元素值（next\[1\]，next\[2\]，next\[6\]）同样是0。

GTG的最长可匹配前缀是G，对应数组中的next\[3\]，元素值是1。

以此类推，  
GTGT 对应 next\[4\]，元素值是2。  
GTGTG 对应 next\[5\]，元素值是3。

有了next数组，我们就可以通过已匹配前缀的下一个位置（坏字符位置），快速寻找到最长可匹配前缀的下一个位置，然后把这两个位置对齐。

比如下面的场景，我们通过坏字符下标5，可以找到next\[5\]=3，即最长可匹配前缀的下一个位置：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 4]  
说完了next数组是什么，接下来我们再来思考一下，如何事先生成这个next数组呢？

由于已匹配前缀数组在主串和模式串当中是相同的，所以我们仅仅依据模式串，就足以生成next数组。

最简单的方法是从最长的前缀子串开始，把每一种可能情况都做一次比较。

假设模式串的长度是m，生成next数组所需的最大总比较次数是1+2+3+4+…+m-2 次。

显然，这种方法的效率非常低，如何进行优化呢？

我们可以采用类似“动态规划”的方法。首先next\[0\]和next\[1\]的值肯定是0，因为这时候不存在前缀子串；从next\[2\]开始，next数组的每一个元素都可以由上一个元素推导而来。

已知next\[i\]的值，如何推导出next\[i+1\]呢？让我们来演示一下上述next数组的填充过程：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 5]  
如图所示，我们设置两个变量i和j，其中i表示“已匹配前缀的下一个位置”，也就是待填充的数组下标，j表示“最长可匹配前缀子串的下一个位置”，也就是待填充的数组元素值。

当已匹配前缀不存在的时候，最长可匹配前缀子串当然也不存在，所以i=0，j=0，此时next\[0\] = 0。

接下来，我们让已匹配前缀子串的长度加1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 11]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 12]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 13]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][2020030117333129.png]  
![在这里插入图片描述][20200301173342894.png]  
![在这里插入图片描述][20200301173351814.png]

[20200301172159346.png]: https://img-blog.csdnimg.cn/20200301172159346.png
[20200301172225844.png]: https://img-blog.csdnimg.cn/20200301172225844.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301172325747.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200301172408607.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200301172442395.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[20200301172501878.png]: https://img-blog.csdnimg.cn/20200301172501878.png
[20200301172528525.png]: https://img-blog.csdnimg.cn/20200301172528525.png
[20200301172546542.png]: https://img-blog.csdnimg.cn/20200301172546542.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200301172614285.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200301172803366.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020030117283992.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200301172858403.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200301172926218.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200301173036968.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200301173052714.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200301173127899.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200301173145141.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200301173207855.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/2020030117322811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 14]: https://img-blog.csdnimg.cn/20200301173306688.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[2020030117333129.png]: https://img-blog.csdnimg.cn/2020030117333129.png
[20200301173342894.png]: https://img-blog.csdnimg.cn/20200301173342894.png
[20200301173351814.png]: https://img-blog.csdnimg.cn/20200301173351814.png