# KMP详解

By [ff](https://paragraph.com/@ff-4) · 2022-02-08

---

* * *

KMP
===

**\- KMP算法时间的复杂度是O(m+n)，主要优点是：主串不回溯**

### 一、示例图

![](https://storage.googleapis.com/papyrus_images/d126cc8bd588d3f0d38f7660e53142d94f05b5dd2a50b0c14775e76295eacaf9.png)

![](https://storage.googleapis.com/papyrus_images/5759809d719430a70775782fdd53e0b36d71b0d2f6aa9b83197199cee9b1ffc7.png)

**剖析的例子题**

    p作为模式串'aabaac'      s作为主串'aabaabaabaac'
    

**1** . 首先我们先下课

![](https://storage.googleapis.com/papyrus_images/527f6a9e25a50731acc8a58b0a6c08042d3128c48865ee94e98da3dac8931151.png)

**2** . 主串一直往前走，模式串进行比较

    ①
    a a b a a  b a a b a a c
    a a b a a 'c'                
    此时可以看到位于模式串的第'六位'字母c 与主串发生不匹配，这时去找next数组第六位，'next[6]=3'
    那么此时回退到第三位根据公式'j=next[j]'
    
    ②
    a a b a a b a a b a a c
          a a b a a'c' 
    此时可以看到又是第六位字母'c'发生不匹配,仍然回退到'j=next[j]'-->相当于回退三位
    
    ③
    a a b a a b a a b a a c
                a a b a a c
    此时终于 '全部匹配'
    

**上面的例题的方法二**

![](https://storage.googleapis.com/papyrus_images/f4022e768a1963aace337d4caedbf49c40bb5cbadd2059983d4b528af06fcdd3.png)

    1. 首先我们先将模式串的前后缀的部分匹配值求出，如'例1图'
    2. 这时我们进行模拟匹配的时候，就可以使用公式 '右移位数 = 已匹配的字符数-对应的部分匹配值'    
     ①
    a a b a a  b a a b a a c
    a a b a a 'c'  
    此时第六位不匹配，那么我们看到第五位'a'匹配值是'2',已经匹配的是'5'所以使用公式
    '5-2=3'   此时我们将模式串向后移动三位得到②
    
    ②
    a a b a a b a a b a a c
          a a b a a'c' 
    同理与上面思路相同，仍然是'5-2=3' 将模式串向后移动三位得到③
    
    ③
    a a b a a b a a b a a c
                a a b a a c
    

**彩蛋**

*   **到这里，大家重看图1，我们要求看的**`next`其实就是将图1的图
    
*   _匹配值_`整体向右一位`，不是很神奇！

---

*Originally published on [ff](https://paragraph.com/@ff-4/kmp)*