理解kmp算法

末蓝、 2022-03-26 01:56 339阅读 0赞

最近分配到任务需要做一次技术分享，主题是kmp算法，总结笔记如下：

### 1.背景 ###

字符匹配问题（模式匹配问题） 给定目标字符串T，和模板字符串P，求T中是否包含P？P在T中的起始位置是多少？

主串：用模式串去匹配的串

模式串：待定位的子串

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70][]

### 2. 传统匹配过程 ###

1. 主串指针i，模式串指针j，下标从0开始：（这里的指针指：数组索引下标）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 1][]

2. 当满足字符相匹配时，i++, j++

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 2][]

3. 失去配对时，指针i回溯到i-j+1的位置，j回溯到0的位置![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 3][]

4. 指针再次移动，开始下一轮比较：此时i=1 , j=0（每一轮i的起始位置是不同的，即 i-j+1）

![20190311091820792.png][]

5. 当i<t.length && j<p.length长度时，执行以上循环。当跳出循环时，判断j的索引值是否等于j字符串长度，是则返回 i-j ；否则返回-1

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 4][]

6. 代码如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 5][]

### 3. 存在问题 ###

在人为进行操作时，j的移位是不会只移动一位的，我们会直接移动到第二个b所在的结果，为什么，因为我们在第一次扫描时已经知道了前面的信息了（即最前面只有一个b)。即下图btbt这个字符串信息。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 6][]

### 4. 解决方案 ###

利用已经匹配的字符信息，保证i指针不回溯，j回溯到它该去的地方。让模式串尽量地移动到有效的位置。

问题：j指针回溯的位置如何确定（即回溯多少位）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 7][]

### 5.kmp算法示意 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 8][]

### 6. 部分匹配表PMT(Partial Match Table) ###

前缀（不包括最后一位），后缀（不包括最前一位），最大交集长度

对于上面的字符串btbtbtru，按前缀和后缀进行划分，按照长度划分   以：btbtbtru为例

<table> 
 <tbody> 
 <tr> 
 <td> &nbsp; 字符串长度 </td> 
 <td> 索引值 </td> 
 <td> 字符串 </td> 
 <td> 前缀集合 </td> 
 <td> 后缀集合 </td> 
 <td> 交集最大长度 </td> 
 </tr> 
 <tr> 
 <td> 1 </td> 
 <td> 0 </td> 
 <td> b </td> 
 <td> 无 </td> 
 <td> 无 </td> 
 <td> 0 </td> 
 </tr> 
 <tr> 
 <td> 2 </td> 
 <td> 1 </td> 
 <td> bt </td> 
 <td> {b} </td> 
 <td> {t} </td> 
 <td> 0 </td> 
 </tr> 
 <tr> 
 <td> 3 </td> 
 <td> 2 </td> 
 <td> btb </td> 
 <td> {b},{bt} </td> 
 <td> {tb},{b} </td> 
 <td> 1 </td> 
 </tr> 
 <tr> 
 <td> 4 </td> 
 <td> 3 </td> 
 <td> btbt </td> 
 <td> {b},{bt},{btb} </td> 
 <td> {tbt},{bt},{b} </td> 
 <td> 2 </td> 
 </tr> 
 <tr> 
 <td> 5 </td> 
 <td> 4 </td> 
 <td> btbtb </td> 
 <td> {b},{bt},{btb},{btbt} </td> 
 <td> {tbtb},{btb},{bt},{t} </td> 
 <td> 3 </td> 
 </tr> 
 <tr> 
 <td> 6 </td> 
 <td> 5 </td> 
 <td> btbtbt </td> 
 <td> {b},{bt},{btb},{btbt},{btbtb} </td> 
 <td> {tbtbt},{btbt},{tbt},{bt},{t} </td> 
 <td> 4 </td> 
 </tr> 
 <tr> 
 <td> 7 </td> 
 <td> 6 </td> 
 <td> btbtbtr </td> 
 <td> {b},{bt},{btb},{btbt},{btbtb},{btbtbt} </td> 
 <td> {tbtbtr},{btbtr},{tbtr},{btr},{tr},{r} </td> 
 <td> 0 </td> 
 </tr> 
 <tr> 
 <td> 8 </td> 
 <td> 7 </td> 
 <td> btbtbtru </td> 
 <td> {b},{bt},{btb},{btbt},{btbtb},{btbtbt},{btbtbtr} </td> 
 <td> {tbtbtru},{btbtru},{tbtru},{btru},{tru},{ru},{u} </td> 
 <td> 0 </td> 
 </tr> 
 </tbody> 
</table>

### 7.列得如下表格 ###

<table> 
 <tbody> 
 <tr> 
 <td> Char </td> 
 <td> b </td> 
 <td> t </td> 
 <td> b </td> 
 <td> t </td> 
 <td> b </td> 
 <td> t </td> 
 <td> r </td> 
 <td> u </td> 
 </tr> 
 <tr> 
 <td> index </td> 
 <td> 0 </td> 
 <td> 1 </td> 
 <td> 2 </td> 
 <td> 3 </td> 
 <td> 4 </td> 
 <td> 5 </td> 
 <td> 6 </td> 
 <td> 7 </td> 
 </tr> 
 <tr> 
 <td> value </td> 
 <td> &nbsp;0 </td> 
 <td> 0 </td> 
 <td> 1 </td> 
 <td> 2 </td> 
 <td> 3 </td> 
 <td> 4 </td> 
 <td> 0 </td> 
 <td> 0 </td> 
 </tr> 
 </tbody> 
</table>

### 8. value值数组向后偏移得到next数组 ###

如果是在 j 位 失配，那么影响 j 指针回溯的位置的其实是第 j −1 位的 PMT 值，故value值+1向后偏移，第0位补-1值，得到如下next值

<table> 
 <tbody> 
 <tr> 
 <td> char </td> 
 <td> b </td> 
 <td> t </td> 
 <td> b </td> 
 <td> t </td> 
 <td> b </td> 
 <td> t </td> 
 <td> r </td> 
 <td> u </td> 
 </tr> 
 <tr> 
 <td> index </td> 
 <td> 0 </td> 
 <td> 1 </td> 
 <td> 2 </td> 
 <td> 3 </td> 
 <td> 4 </td> 
 <td> 5 </td> 
 <td> 6 </td> 
 <td> 7 </td> 
 </tr> 
 <tr> 
 <td> value </td> 
 <td> &nbsp;0 </td> 
 <td> 0 </td> 
 <td> 1 </td> 
 <td> 2 </td> 
 <td> 3 </td> 
 <td> 4 </td> 
 <td> 0 </td> 
 <td> 1 </td> 
 </tr> 
 <tr> 
 <td> next </td> 
 <td> -1 </td> 
 <td> 0 </td> 
 <td> 0 </td> 
 <td> 1 </td> 
 <td> 2 </td> 
 <td> 3 </td> 
 <td> 4 </td> 
 <td> 0 </td> 
 </tr> 
 </tbody> 
</table>

j已经在最左边了，不可能再移动了，这时候要应该是i指针后移。所以在代码中才会有next\[0\] = -1;这个初始化

### 9.如何使用这个表来加速字符串的查找 ###

（j即为扫过部分匹配的字符长度）

对于上面的模式字符串btbtr，按前缀和后缀进行划分，按照长度划分   btbtr

<table> 
 <tbody> 
 <tr> 
 <td> 字符串长度 </td> 
 <td> 索引值 </td> 
 <td> 字符串 </td> 
 <td> 前缀集合 </td> 
 <td> 后缀集合 </td> 
 <td> 交集最大长度 </td> 
 <td> next </td> 
 </tr> 
 <tr> 
 <td> 1 </td> 
 <td> 0 </td> 
 <td> b </td> 
 <td> 无 </td> 
 <td> 无 </td> 
 <td> 0 </td> 
 <td> -1 </td> 
 </tr> 
 <tr> 
 <td> 2 </td> 
 <td> 1 </td> 
 <td> bt </td> 
 <td> {b} </td> 
 <td> {t} </td> 
 <td> 0 </td> 
 <td> 0 </td> 
 </tr> 
 <tr> 
 <td> 3 </td> 
 <td> 2 </td> 
 <td> btb </td> 
 <td> {b},{bt} </td> 
 <td> {tb},{b} </td> 
 <td> 1 </td> 
 <td> 0 </td> 
 </tr> 
 <tr> 
 <td> 4 </td> 
 <td> 3 </td> 
 <td> btbt </td> 
 <td> {b},{bt},{btb} </td> 
 <td> {tbt},{bt},{b} </td> 
 <td> 2 </td> 
 <td> 1 </td> 
 </tr> 
 <tr> 
 <td> 5 </td> 
 <td> 4 </td> 
 <td> btbtr </td> 
 <td> {b},{bt},{btb},{btbt} </td> 
 <td> {tbtr},{btr},{tr},{r} </td> 
 <td> 0 </td> 
 <td> 2 </td> 
 </tr> 
 </tbody> 
</table>

### 10.求next数组的过程 ###

求next数组的过程：与自身匹配，前后缀最大长度，故进行错开一位。以模式字符串为主字符串，以模式字符串的前缀为目标字符串。

就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。 在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示：

![2019031109211890.png][]

注意：这里的k不是指针，而是在j位置时的next value值（记住一句话就行了，k的值是当前i对应的next值，k也就是前面匹配成功的字符数）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 9][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 10][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 11][]

11.代码小结

①. 求next数组过程中，k的值，即当前 j 值下的next数组对应的值，只要k>0, 其自身匹配从串之前相应量的字符必定匹配。

②. 因为是错开匹配的，当不匹配时，这里的“主串”与“从串”进行对比相当于主串与自己的前 k+1 项进行比对。

③. 能进到 if 执行体里面，除了最开始k = -1的初始化，说明当前匹配成功，故i++;; 当前j的next值为k，即成功匹配了k位（加上当前指向的，即k++）。

④. 能进到 else 执行体里，说明当前 i 指向的字符与 k 指向的不匹配，k回溯到当前 i 指向位置的next\[i\] 值，即前面已经匹配成功的位置+1。

### 12.kmp与传统做法的对比 ###

传统做法（时间复杂度：O（mxn）m为主串长度，n为模式串长度）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 12][]

kmp算法\*（时间复杂度：O(m+n),m为主串长度，n为模式串长度）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 13][]

附源代码：[https://gitee.com/jiayuan1234/kmp][https_gitee.com_jiayuan1234_kmp]

细节处待完善。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70]: /images/20220326/a7832aa37b63423bb1efc2e05edd7c1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 1]: /images/20220326/860dd5a049bd4f7891b44bc01cdf65e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 2]: /images/20220326/1befe5d3357c4be8a62f0fef531742c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 3]: /images/20220326/96f8d7601af943959c14b46d35a5ac11.png
[20190311091820792.png]: /images/20220326/b3b73d43d51949c29b00177a80e953d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 4]: /images/20220326/b45636ee330c4efb927fdc234833d70c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 5]: /images/20220326/4cd453ee7543493c9fc1bd84c452ca47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 6]: /images/20220326/0e65eb291c874d5298232e9d6d174d34.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 7]: /images/20220326/e0607f53a7ac42f59f363aaa598eb11b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 8]: /images/20220326/7fccf3d6e5c4476f9ed23adc4337936e.png
[2019031109211890.png]: /images/20220326/7123953d7db04a669bb6ca154b039184.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 9]: /images/20220326/c108d5ab985a422fa1dd24e4036de521.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 10]: /images/20220326/21343cc714b14c3fa806bd8d234aebd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 11]: /images/20220326/7042d307806a4294b1e7946e2426bb3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 12]: /images/20220326/a0f055c3157545be9f75ce485a3acbaf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX2ppYXl1YW4_size_16_color_FFFFFF_t_70 13]: /images/20220326/2ee7b29a476e44a48d7c16c6e078184e.png
[https_gitee.com_jiayuan1234_kmp]: https://gitee.com/jiayuan1234/kmp