关键词：
KMP算法，又称作“看猫片”算法（误），是一种改进的字符串模式匹配算法，可以在O(n+m)的时间复杂度以内完成字符串的匹配操作，其核心思想在于：当一趟匹配过程中出现字符不匹配时，不需要回溯主串的指针，而是利用已经得到的“部分匹配”，将模式串尽可能多地向右“滑动”一段距离，然后继续比较。
1. 朴素的字符串模式匹配算法
求一个字符串（模式串）在另一个字符串（主串）中的位置，称为字符串模式匹配。
在朴素的字符串模式匹配算法中，我们对主串S和模式串T分别设置指针i和j，假设字符串下标从0开始，初始时i和j分别指向每个串的第0个位置。在第n趟匹配开始时，i指向主串S中的第n-1个位置，j指向模式串T的第0个位置，然后逐个向后比较。若T中的每一个字符都与S中的字符相等，则称匹配成功，否则，当遇到某个字符不相等时，i重新指向S的第n个位置，j重新指向T的第0个位置，继续进行第n+1趟匹配。
例如，我们对模式串T=“abaabcac”和主串S=“abcabaabaabcacb”进行匹配。如图1.1，此时正在进行第4趟匹配，S[3...7]与T[0...4]均相等，但当i=8，j=5时，S[8]与T[5]不相等，匹配失败。于是，置i=4，j=0，相当于将模式串向右移动一位后，重新开始下一趟匹配，如图1.2。
利用此种方法进行字符串匹配，最坏情况下时间复杂度为O(n*m)，其中n和m分别为主串和模式串的长度。
2. 改进的字符串模式匹配算法——KMP算法
在上面的例子中，我们可以看到，当i=8，j=5时，S[8]与T[5]不相等，于是置i=4，j=0，相当于将模式串向右移动一位，再开始下一趟匹配。然而，通过观察我们可以发现，之后的两趟匹配，即i=4，j=0以及i=5，j=0都是不必要的。这是因为，在之前的一趟匹配过程中，我们已经部分匹配了T的子串“abaab”。此时将T向右移动一位，则相当于对T中的“abaab……”与S中的“baab……”进行匹配，显然无法匹配成功。继续右移T，则相当于对T中的“abaab……”与S中的“aab……”进行匹配，依然无法匹配成功。只有当T向右移动3位后，此时对T中的“abaab……”与S中的“ab……”进行匹配，才会有成功的可能，也就有必要向后继续进行比较。如图2.1。
因此，当i=8，j=5，T的子串“abaab”已经匹配成功，而其后一位字符却不相等时，不必回溯i指针，置i=8，j=2，继续向后比较，相当于将T向右移动3位，并从T的第3位开始向后比较。如图2.2。
这就是KMP算法的基本思路。对于模式串T中的前j个字符组成的子串，设置数组next[j]存放一个值，当模式串T匹配至第j个字符时与主串不相等，则i指针不变，将j指针置为next[j]的值，然后继续进行比较。在上例中，串“abaab”为模式串T的前5个字符组成的子串，令next[5]=2，当i=8，j=5时，S[8]与T[5]不相等，于是置i=8，j=next[j]=next[5]=2，然后继续进行比较。
因此，KMP算法的核心在于求出数组next，即模式串T中每一个长度为j (0<j<T.length) 的前缀所对应的next[j]的值。
next数组求解算法
在求解next数组前，我们首先需要理解next数组的含义。回到前面的例子，当T的子串“abaab”的下一个字符与主串不相等时，主串的指针i不变，j回溯至2，指向T的第3个字符，其本质是因为串“abaab”的前缀和后缀有一个长度为2的最长公共串“ab”，因此我们省略了前缀“ab”和后缀“ab”的比较过程，直接对它们的后一个字符，即T[2]和S[8]进行比较。
再看另一个例子，假设有模式串T=“abacaabadad”，其已部分匹配完T[0...7]，即“abacaaba”，在匹配T[8]时遇到匹配失败，因T[0...7]的前缀和后缀有长度为3的最长公共串“aba”，因此next[8]=3，置j=next[j]=next[8]=3，i不变，然后从T[3]，即T的第4个字符开始比较。如图2.3。
总之，对于模式串T，next[j]代表了T的前j个字符组成的子串中，其前缀和后缀的最长公共串的长度。
求解字符串T的next数组的算法如下：
- next[0]=-1, next[1]=0。
- 在求解next[j]时，令k=next[j-1]，
比较T[j-1]与T[k]的值，
a. 若T[j-1]等于T[k]，则next[j]=k+1。b. 若T[j-1]不等于T[k]，令k=next[k]，若k等于-1，则next[j]=0，否则跳至3。
下面以模式串T=“abaabcac”为例，给出求next数组的过程：
- next[0]=-1, next[1]=0。
- 当j=2时，k=next[j-1]=next[1]=0，由于T[j-1]=T[1]=‘b’，T[k]=T[0]=‘a’，T[j-1]不等于T[k]，令k=next[k]=next[0]=-1，因此next[2]=0。
- 当j=3时，k=next[j-1]=next[2]=0，由于T[j-1]=T[2]=‘a’，T[k]=T[0]=‘a’，T[j-1]等于T[k]，因此next[3]=k+1=1。
- 当j=4时，k=next[j-1]=next[3]=1，由于T[j-1]=T[3]=‘a’，T[k]=T[1]=‘b’，T[j-1]不等于T[k]，令k=next[k]=next[1]=0。此时T[k]=T[0]=‘a’，T[j-1]等于T[k]，因此next[3]=k+1=1。
- 当j=5时，k=next[j-1]=next[4]=1，由于T[j-1]=T[4]=‘b’，T[k]=T[1]=‘b’，T[j-1]等于T[k]，因此next[5]=k+1=2。
- 当j=6时，k=next[j-1]=next[5]=2，由于T[j-1]=T[5]=‘c’，T[k]=T[2]=‘a’，T[j-1]不等于T[k]，令k=next[k]=next[2]=0。此时T[k]=T[0]=‘a’，T[j-1]不等于T[k]，再令k=next[k]=next[0]=-1，因此next[6]=0。
- 当j=7时，k=next[j-1]=next[6]=0，由于T[j-1]=T[6]=‘a’，T[k]=T[0]=‘a’，T[j-1]等于T[k]，因此next[7]=k+1=1。
将next数组全部求出之后，只需在简单的匹配算法上稍作修改，便得到了KMP的匹配算法：当模式串T匹配至第j个字符时匹配失败，i指针不变，将j指针置为next[j]的值，若j的值为-1，则将i和j同时加1。随后继续进行逐个的比较。
下面以模式串T=“abaabcac”和主串S=“abcabaabaabcacb”进行匹配为例，给出KMP匹配算法的全过程。
之前已经求得模式串T的next数组为[-1, 0, 0, 1, 1, 2, 0, 1]。
- 初始时，i=0，j=0，匹配成功。
- i=1，j=1，匹配成功。
- i=2，j=2，匹配失败。
- i=2，j=next[2]=0，匹配失败。
- i=2，j=next[0]=-1，匹配失败。
- i=2+1=3，j=-1+1=0，匹配成功。
- i=4，j=1，匹配成功。
- i=5，j=2，匹配成功。
- i=6，j=3，匹配成功。
- i=7，j=4，匹配成功。
- i=8，j=5，匹配失败。
- i=8，j=next[5]=2，匹配成功。
- 继续向后比较，中间过程均匹配成功，故不再赘述，当i=13，j=7时，模式串匹配完成。
以上就是KMP匹配算法的全过程。总结一下，KMP算法的实质就是以空间换时间，在匹配之前将模式串的一些信息存储起来（next数组），在随后的匹配过程中利用这些信息减少不必要的匹配次数，以提高匹配效率。在实际的应用过程中，简单模式匹配算法的执行时间常常接近于KMP算法，仅当主串与模式串有很多“部分匹配”时，KMP算法才能显著提升性能。
3. KMP算法的Java实现
下面给出KMP算法的Java代码。整个算法分为两部分，一是next数组的求解，二是KMP匹配过程。
public class KMP
/**
* 求出一个字符数组的next数组
* @param t 字符数组
* @return next数组
*/
public static int[] getNextArray(char[] t)
int[] next = new int[t.length];
next[0] = -1;
next[1] = 0;
int k;
for (int j = 2; j < t.length; j++)
k=next[j-1];
while (k!=-1)
if (t[j - 1] == t[k])
next[j] = k + 1;
break;
else
k = next[k];
next[j] = 0; //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值
return next;
/**
* 对主串s和模式串t进行KMP模式匹配
* @param s 主串
* @param t 模式串
* @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1
*/
public static int kmpMatch(String s, String t)
char[] s_arr = s.toCharArray();
char[] t_arr = t.toCharArray();
int[] next = getNextArray(t_arr);
int i = 0, j = 0;
while (i<s_arr.length && j<t_arr.length)
if(j == -1 || s_arr[i]==t_arr[j])
i++;
j++;
else
j = next[j];
if(j == t_arr.length)
return i-j;
else
return -1;
public static void main(String[] args)
System.out.println(kmpMatch("abcabaabaabcacb", "abaabcac"));
参考资料及致谢
在学习KMP算法思路的过程中，我大量参考了“王道考研系列”的《数据结构联考复习指导》一书，以及CSDN博主v_JULY_v的文章：从头到尾彻底理解KMP，特此鸣谢。
同时感谢微博博主@回忆专用小马甲和实验室的大红袍CocoXu提供的大量猫片，让我在学习KMP算法的过程中拥有持续的动力。
文章中如有错误，欢迎指正！
❤️详解kmp算法(代码片段)
由于KMP算法描述起来很抽象，所以很多人难以理解，那么这篇博客将帮你解决这个难题，带你彻底了解KMP的原理以及实现。KMP算法是一种改进的字符串匹配算法，KMP算法的核心是利用匹配失败后的信息，尽量... 查看详情
kmp算法详解以及java代码实现(代码片段)
详细介绍了KMP算法的原理以及Java代码实现。我们此前学了前缀树Trie的实现原理以及Java代码的实现。Trie树很好，但是它只能基于前缀匹配实现功能。但是如果我们的需求是：一个已知字符串中查找子串，并且子串并... 查看详情
数据结构kmp算法配图详解（超详细）(代码片段)
文章目录一、什么是KMP算法？二、KMP算法的解决题型三、模式串移动距离的判断（next数组）四、KMP算法的具体实现五、KMP算法的时间复杂度六、next数组的改进--nextval数组及具体代码七、最后的话一、什么是KMP算法... 查看详情
ac自动机算法详解以及java代码实现(代码片段)
详细介绍了AC自动机算法详解以及Java代码实现。文章目录1概念和原理2节点定义3构建Trie前缀树3.1案例演示4构建fail失配指针4.1案例演示5匹配文本5.1案例演示6完整实现7总结8其他参考1概念和原理AC自动机(Aho-Corasickautomaton)算法于197... 查看详情
kmp算法详解(代码片段)
文章目录前言例题引入简单算法BF经典算法KMPkmp理解难点1kmp理解难点2kmp最难理解点3kmp代码前言对于kmp的鼎鼎大名,不只是博主自己,想必还有更多小伙子们听说过,也相信都去了解过,博主亦是这样,但是真正去理解这个过程,确是异... 查看详情
ac自动机算法详解以及java代码实现(代码片段)
详细介绍了AC自动机算法详解以及Java代码实现。文章目录1概念和原理2节点定义3构建Trie前缀树4构建fail失配指针5匹配文本6案例演示7总结1概念和原理一般的字符串匹配算法都是匹配一个子串，例如KMP、Trie，那么如果同时... 查看详情
图解kmp算法原理及其代码分析(代码片段)
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。该算法是字符串两大难点算法之一。在这里我想对提出该算法的三位... 查看详情
详解kmp算法(代码片段)
前言KMP算法是学习数据结构 中的一大难点，不是说它有多难，而是它这个东西真的很难理解（反正我是这么感觉的，这两天我一直在研究KMP算法，总算感觉比较理解了这套算法，在这里我将自己的思路分享给大家，也是检验... 查看详情
kmp算法详解——多图，多例子（c语言）(代码片段)
目录前言1.KMP算法是什么？2.为什么需要KMP算法？2.1主串找字串2.2暴力求解3.KMP准备工作3.1字符串的前后子串3.2最大前后相等子串3.3最大前后相等子串练习4.KMP算法4.1简看KMP算法5Next数组 5.1j该回溯的位置 5.2学会计算... 查看详情
kmp算法详解v1(代码片段)
引言KMP算法指的是字符串模式匹配算法，问题是：在主串T中找到第一次出现完整子串P时的起始位置。该算法是三位大牛：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的，以其名字首字母命名。在网上看了不少对KMP算法的解析，大多写的... 查看详情
拓展kmp算法详解(代码片段)
...T在S中找到匹配而且起始位置是i，这就解释了为什么这个算法叫做拓展 查看详情
kmp算法实现(代码片段)
KMP算法实现packagecom.wwz.kmp;importjava.util.Arrays;publicclassKmpDeom publicstaticvoidmain(String[]args) //TODO自动生成的方法存根 Stringstr1="aabcdabd"; Stringstr2="abcdabd"; int[]a& 查看详情
javajava实现的kmp算法(代码片段)
kmp算法的两种实现(代码片段)
前言朴素子字符串查找算法KMP算法的基本思想基于DFA的KMP实现基于PMT的KMP实现历史渊源&DFA&PMT结语参考链接前言KMP算法在LeetCode刷题的过程中看见过好几次，这几天终于去学习了一下，然后，我就发现，Google出来的KMP和我书... 查看详情
kmp算法(代码片段)
KMP算法写OJ时做到字符串匹配问题，用暴力算法结果超出时间限制了，其实早就知道这种问题可以用kmp算法解决，但是我一直懒得学，于是借助这个OJ来记录一下学习kmp算法的一些个人理解文章目录KMP算法字符串匹... 查看详情
kmp算法(代码片段)
KMP算法写OJ时做到字符串匹配问题，用暴力算法结果超出时间限制了，其实早就知道这种问题可以用kmp算法解决，但是我一直懒得学，于是借助这个OJ来记录一下学习kmp算法的一些个人理解文章目录KMP算法字符串匹... 查看详情
kmp算法(代码片段)
KMP算法给定文本串A、模式串B，求模式串B在文本串A中出现的次数。设文本串A的长度为n，模式串B的长度为m暴力：二重循环+回溯复杂度O(n*m)KMP:将复杂度优化到O(n+m)本篇文章是我初学KMP算法所写，如果有错误欢迎指出另外本文的KM... 查看详情
kmp算法(代码片段)
KMP算法KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达... 查看详情