一、什么是KMP

说到KMP，先说一下KMP这个名字是怎么来的，为什么叫做KMP呢。

因为是由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP。

二、KMP有什么用

  • KMP主要应用在字符串匹配上。
  • KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
  • 所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

三、什么是前缀表

  • next数组就是一个前缀表（prefix table）。
  • 前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
  • 前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

四、最长相等前后缀

  • 字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
  • 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
  • 前缀表要求的就是相同前后缀的长度。

五、使用next数组来匹配

  • 以下我们以前缀表统一减一之后的next数组来做演示。
  • 有了next数组，就可以根据next数组来 匹配文本串s，和模式串t了。
  • 注意next数组是新前缀表（旧前缀表统一减一了）。
  • 匹配过程动画如下：

六、时间复杂度

  • 其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。
  • 所以整个KMP算法的时间复杂度是O(n+m)的。
  • 暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大的提高的搜索的效率。