KMP，一个让无数考研科班学子闻风丧胆的匹配算法，但也正应和了高中老班经常说的那样，很难的东西，考察起来会很简单，KMP在408中只考察过两次，且考察方式十分的简单，本文分为两个方面，第一大模块介绍考研中需要掌握的KMP，学有余力的同学可以看一下第二部分，KMP的代码实现，本文会对KMP的描述十分的详细 (因为博主怕以后忘记，咳咳咳，还得靠这篇复习)

考研中对KMP的考察为：会简单模拟KMP过程，并且可求出KMP的next数组即可

KMP是对朴素版字符串匹配算法的优化，我们这里还是举栗子说明： 下面小故事的场景为一个班级中有一位老师(晶姐)，两个学生：聪明的博主以及枭哥

晶姐今天丢给博主和枭哥两个人一个问题： “这儿有两个字符串，字符串P是ababa，字符串Q是aba，现在你们两个给我找出来P中所有出现Q的位置，并且告诉我怎么找出来的”，说罢，便走到一旁开始喝茶。

听完这个问题，枭哥立刻站起来，说：“老师，我有一个笨办法” 好家伙，这可把博主吓了一跳：这人脑子啥时候这么好了 (不是

枭哥可不管博主心里怎么想，继续说到："设两个字符串的起点分别为i和j，然后依次对比，如果P[i] == Q[j]的话，就继续往后匹配，执行i ++， j ++，否则的话，让i移动到i最开始位置的后一个位置(即i最开始 = 1，比如发生不匹配的时候i = 3，那么让i = 2)，然后让j的值重新指回1" 晶姐点了点头 “不错，这个是个方法，直接暴力的去做就可以，假设P的长度为n，Q的长度为m，那么，时间复杂度为：O(nm)，辰chen，你有什么想法么？”

果然，还是得看聪明的我 (逃 “枭哥的办法太笨了”，博主悠悠站起身 “接下来请欣赏我的表演” “枭哥这个办法时间复杂度太高，为什么高呢？因为对于每次发生不匹配的情况的时候，i都需要回溯，我们如果可以设计出这么一个东西，可以不让i发生回溯，即我们的i值只能一直变大直到遍历完整个P串，那么我们的算法显然是要变快了不少”

晶姐继续问道：“那应该怎么处理才能让i不发生回溯呢？” “啊这，这就不知道了”，博主说到 那你装 ** 呢！？”，枭哥吼道 “咳咳” “好啦好啦，都安静，辰chen的思维还是很不错的，这个思维就叫做KMP算法，即不让i发生回溯，i是始终往后走的，KMP的时间复杂度为O(n + m)，下面就让老师给大家讲解KMP算法中，辰chen不会处理的地方究竟是什么”

首先声明一点：本文中所有的字符串(数组)，下标均为从1开始，并非从0开始，这一点需要 注意再注意 KMP算法的核心就是next数组，介绍next数组之前，引入几个概念：子串，前缀，后缀 子串：串中任意多个 连续 的字符组成的子序列称为该串的子串 前缀：除了最后一个字符，字符串所有的头部子串 后缀：除了第一个字符，字符串所有的尾部子串

只有Q(短串)才有next数组，因为我们要求KMP算法中，长串的i不发生回溯，下面介绍next数组： 数组的定义：next[j]表示的为串的[1 ~ j - 1]中前后缀相等的最大长度 + 1，特别的，我们规定next[1] = 0 桥都嘛得！！！，看不懂上面说的么得关系，下面举栗子就懂了：

比如我们的Q串为：abaabc next[1] = 0（特殊规定） next[2]：按照上述定义为串的[1 ~ 1]中的前后缀相等的最大长度 + 1，显然，按照前后缀的定义，[1 ~ 1]的前后缀都为空，故前后缀相等的最大长度为0，即next[2] = 1 next[3]：串[1 ~ 2]为ab，前缀为a，后缀为b，显然a != b，故next[3] = 1 next[4]：串[1 ~ 3]为aba，前缀有三个：ab，a，空；后缀有三个ba，a，空，显然ab != ba，但是有a == a，即前后缀相等的最大长度为1，故next[4] = 2 next[5]：串[1 ~ 4]为abaa，前缀分别为：aba，ab，a，空；后缀分别为：baa，aa，a，空；显然，前后缀相等的最大长度还是1，故next[5] = 2 next[6]：串[1 ~ 5]为abaab，前缀分别为：abaa，aba，ab，a，空；后缀分别为：baab，aab，ab，b，空；显然有前缀ab和后缀ab是相等的，故前后缀相等的最大长度为2，即next[6] = 3

这就是我们预处理的next数组，按照上述栗子模拟后，大家应该懂得next数组应该如何去求了，next[1] = 0为特殊规定，其余的next[i] = 串的[1 ~ j - 1]中前后缀相等的最大长度 + 1，对于考研而言，能够自己手动去模拟next数组如何去求已经足够了，下面给出两个例题，读者可以自己动手求一下next数组，按照答案进行对比：

1.串aaab的next数组值 2.串ababaaababaa的next数组值

答案： 1.0123 2.011234223456

大家还可以发现一个有趣的规律：next[2] 恒等于 1 这里再强调一个点，有的书是规定next[1] = -1，那么我们只需要让next数组中所有的值都减去1即可

知道如何求出next数组之后，对于考研，我们还需要知道如何模拟KMP的过程，我们还是举栗子去说明： P：abaacabacabaabc Q：abaabc 刚才我们已经求得了Q的next数组，接下来，我们开始比较，令i = 1(指向P的第一个位置)，j = 1(指向Q的第一个位置)，只要相等，就让i ++, j ++;，否则，我们让i不变，j = next[j]，可能大家看到这里很懵，不知道为什么要让j = next[j]，我们动手模拟一下就会知道了： 观察P和Q，那么当i == 5, j == 5的时候发生不匹配，我们要求i不变，让j = next[j]，即j退回到j = 2，这时候对P的第5个位置和Q的第2个位置继续进行比较即可，为什么呢？因为当我们的next指的为前后缀相等的最大长度 + 1，当我们的第j个位置发生不匹配，证明前[1 ~ j - 1]都是匹配的 如图所示，我们只需要让c和b比较即可，相当于当我们发生不匹配的时候，我们去看当前Q的前缀，找到前后缀相等最大的值然后比较后一位，比如上述图片中，前缀为abaa，前后缀想等的最大值为1，那么我们从1 + 1的位置进行比较即可 继续比较会发现，我们的j最终变成了0，那么这个时候，就证明包涵i这个位置的所有子串都不能和Q相匹配，故让i ++, j ++;

读者可以自己下去模拟后续的匹配过程，一定要自己手动模拟才可以理解KMP的奥义！

关于KMP，听了王道的课，听了AcWing的课，感觉起来还是王道的课要更容易理解一些，这里给出王道的KMP模板和AcWing的KMP模板，读者可以自行比较考虑，王道的模板为C语言，AcWing为C++，关于模板：直接背即可