什么是KMP算法

1. 名字含义

KMP算法全称Knuth-Morris-Pratt算法，取自三位发明者——D.E. Knuth（高德纳）、J.H. Morris（莫里斯）和V.R. Pratt（普拉特）——姓氏的首字母。这三位计算机科学家于1977年联合提出了这一算法。

2. 算法功能

简单说，KMP算法就是用来解决“在一大段文字里快速找到某个关键词”的问题。

如果用大白话来讲它的运作方式，可以这样理解：

普通的暴力匹配，是一个字一个字地挪动关键词，每次对不上了，就退回起点，把关键词整体往右挪一位，从头再比，像一把“死板”的尺子。

而KMP算法，则是一把“聪明”的尺子。它会在匹配之前先“打量”一下关键词内部的重复规律。当遇到对不上的字符时，它不会只挪一位，而是利用提前记下的规律，一次跳跃好几格，直接跳过那些“用脚想都知道肯定配不上”的位置。整个过程主串的指针一直往前走，从不回退。

3. 意义

KMP算法的出现，把字符串匹配的效率从“一个位置一个位置笨拙地挪”提升到了“跳跃式前进”的智慧层面。

最坏情况下：

• 朴素字符串匹配算法(暴力匹配)：时间复杂度为 O(n×m) 
• KMP算法：时间复杂度为O(n+m)

可见KMP极大程度优化了字符串匹配这件事，让计算机在处理海量文本或长关键词时能节省大量时间。更重要的是，它所蕴含的“利用已知信息避免重复劳动”的思想，成为了算法优化领域的一盏指明灯。

4. 相关名词解释

如下图所示，给了一个例子，让我们在“sadbutsad”这个字符串中，寻找“sad”这个子字符串第一次出现的下标，此时：

• 主串：就是“sadbutsad”
• 子串：就是“sad”

5. 举例

主串：

子串（也叫“模式串”）：

• 暴力匹配的做法

• KMP的做法

解题详细步骤

1. 根据子串，求出next数组（next数组只由子串决定，和主串无关）

上题中，子串ABABC的next数组为[0, 1, 1, 2, 3]

求这个，需要了解一下“最长前后缀”这个概念

举例：

实战案例

待完善