关键词：
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法，由他们的名字首字母组成）。
KMP算法的关键是利用已经部分匹配的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
在介绍KMP之前先说一说朴素解法，也就是最简单的暴力解法，朴素解法是采用穷举的方式一个一个对比达到查找的功能，模式串与主串匹配失败后又要重新从模式串的开头继续匹配，不考虑模式串已经判断过的字符，所以效率差。
下面是朴素解法的实现代码：
int sub_str_index(const char* s, const char* p) // s是主串，p是模式串 { int ret = -1; // ret记录返回值，初始化为-1表示没有找到 int sl = strlen(s); int pl = strlen(p); int len = sl - pl; // len记录主串的查找边界，避免主串剩余字符不足，提高效率 for(int i=0; (ret<0) && (i<=len); i++) // 如果没有找到匹配的，且主串不会到边界 { bool equal = true; // equal用于记录临时的匹配情况，为了下面的循环，默认为真 for(int j=0; equal && (j<pl); j++) // 判断当前位置主串是否与模式串完全匹配 equal = (s[i + j] == p[j]); ret = (equal ? i : -1); // 如果模式串全部匹配成功就返回匹配主串首字符的下标，否则返回-1表示失配 } return ret; }
接下来介绍KMP算法：
KMP算法是利用已知的信息减少无效匹配判断的一种算法。
这是阮一峰的讲解，我觉得非常好，供参考：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
另外youtube上的黄浩杰也讲的不错，方便的朋友可以去看看。
下面这张图来自阮一峰博客，我做了一些修改，用它来举例子：
经过几次查找后，这里模式串的D和主串的空格失配了，为了提高查找效率，我们发现直接把模式串向后移动4位可以更高效的匹配，因为主串当前的3个字符都不能和模式串匹配，从而省去了前面3次匹配的过程，实现效率的提升。
这个例子是要右移4位，4是怎么来的呢，是通过模式串已经匹配的最后一个字符的位置（这里就是模式串的第6个字符B，数组下标为5）减去模式串最长匹配数2得到的，那2又是怎么来的呢，2是模式串前缀与模式串后缀最多能匹配的字符个数，也就是部分匹配值
首先我们要先搞懂什么是前缀、后缀、部分匹配值以及部分匹配表
拿上面的模式串"ABCDABD"来说
前缀就是取从开头到任意一个字符的子串；后缀则是取任意一个字符到末尾的子串；当然长度为0或者为模式串的总长度就没有意义了，所以这两个长度不计算
下面这幅图是在部分匹配成功后又匹配失败的部分匹配值计算演示图；
现在假设需要匹配第7个字符D（数组下标为6），注意D左边的B和A都匹配成功了，这时候直接使用最后一个匹配字符也就是前一个字符B（第6个字符）在前缀中的位置的部分匹配值；最后一个匹配字符是第6个字符B，它所对应的前缀位置通过它自己的部分匹配表记录了（也就是2），这就是说这个字符B和模式串第2个字符（数组下标为1）是对应的，第二个字符B的部分匹配值为0，所以不能匹配的第7个字符的部分匹配值也是0；
最长匹配字符数就是最终的部分匹配值
部分匹配值就是某个后缀最多与前缀匹配的字符个数，上面这张图可以看到前缀是A开头，所以后缀也得是A开头才能匹配，这时候有ABD这个后缀能匹配，再贪婪一点，还能匹配更多吗，发现最多只能匹配2个字符，所以它的部分匹配值就是2；
部分匹配表是记录部分匹配值的一个数据结构，因为我们能匹配的模式串长度是不确定的，所以需要针对每个位置生成一个部分匹配值
这里就要用到KMP算法的部分匹配表了，部分匹配表用于记录模式串前缀与模式串后缀最多能匹配的字符个数；通过这个计数我们就能知道移动的位数了，因为它记录了当前字符最长匹配的字符个数，所以得出下面的公式：
移动位数 = 已匹配的字符数 - 对应的部分匹配值
使用计算公式我们就可以计算出右移的位数，已匹配字符数为6（已匹配ABCDAB），最后一个匹配的字符B的部分匹配表为2，所以右移6-2=4位.
网上很多人把这个部分匹配表写成next数组，我这里根据老师的代码写成了int类型的指针，用堆空间记录，长度与模式串长度一致，每个单位为int类型，等效于int数组。
int* make_pmt(const char* p)· // 部分匹配表生成函数，给定模式串指针作为参数，返回int*记录部分匹配表，可充当数组使用，长度为模式串长度；参数合法性由调用者判断 { int len = strlen(p); int* ret = static_cast<int*>(malloc(sizeof(int) * len)); // 申请堆空间用于记录部分匹配表，使用者需要释放 if( ret != NULL ) // 只有堆空间申请成功才能操作 { int ll = 0; // ll==>longest length，最长部分匹配值，初始化最长部分匹配值为0 ret[0] = 0; // 第一个元素没有匹配的所以直接写为0 for(int i=1; i<len; i++) // 从第二个元素开始遍历 { while( (ll > 0) && (p[ll] != p[i]) ) // 如果已经有匹配过的字符，但是下一个字符不匹配 { ll = ret[ll-1]; // 把ll重置为模式串的第ll个字符的部分匹配值，数组下标从0开始所以要减1，p[11-1]的部分匹配值存储于ret[ll-1]； } if( p[ll] == p[i] ) // 每匹配成功一个字符ll就递增 { ll++; } ret[i] = ll; // 进入下一轮循环前要把ll值保存进部分匹配表，即ret[i]记录p[i]的最长部分匹配表 } } return ret; }
下面是kmp函数：
int String::kmp(const char* s, const char* p) // s主串，p模式串 { int ret = -1; int sl = strlen(s); int pl = strlen(p); int* pmt = make_pmt(p); // 获取子串的部分匹配表，注意该函数返回的是堆空间，用完需要释放 if( (pmt != NULL) && (0 < pl) && (pl <= sl) ) // 只有当部分匹配表获取成功、模式串长度大于0且不超过源串长度的时候才需要计算 { for(int i=0, j=0; i<sl; i++) // for初始化i和j变量，i用于遍历每个主串的字符，j用于记录已匹配的模式串字符数 { while( (j > 0) && (s[i] != p[j]) ) // 有已匹配字符但是后续字符又匹配失败时 { j = pmt[j-1]; // 移动模式串，使模式串第一个字符对齐到主串下一个匹配的字符位置，这是一次性移动，不再是暴力搜索中的每次只移动一次 } if( s[i] == p[j] ) // 如果匹配成功，记录匹配模式串字符个数的j加1 { j++; } if( j == pl ) // 如果当前已匹配的模式串字数与模式串长度相等说明匹配成功 { ret = i + 1 - pl; // 返回匹配源串的第一个字符的下标并跳出循环结束寻找；此时i指向的是匹配的主串的最后一个字符，减去子串长度后等于第一个匹配的字符的前一个，所以要加1往后挪一个 break; } } } free(pmt); // 记得释放部分匹配值生成函数申请的堆空间 return ret; }
子字符查找kmp算法-子串自匹配索引表
publicstaticint[]kmpTable(char[]seq){int[]tbl=newint[seq.length];tbl[0]=1;for(inti=1;i<seq.length;i++){//子串最开始intj=tbl[i-1];//从已经算出的索引开始l1:for(;j<=i;j++){for(intk=0;j+k<=i;k++){if(seq[j+k]==s 查看详情
数据结构开发(14)：kmp子串查找算法(代码片段)
0.目录1.KMP子串查找算法2.KMP算法的应用3.小结1.KMP子串查找算法问题：如何在目标字符串S中，查找是否存在子串P？朴素解法：朴素解法的一个优化线索：示例：伟大的发现：匹配失败时的右移位数与子串本身相关，与目标串无关... 查看详情
算法-kmp算法
1解决问题从一个字符串中查找子串，如果存在返回字串在字符串中的位置。示例：字符串（T）：“BBCABCDABABCDABCDABDE”子串(P)：“ABCDABD”通过算法查找字串P在字符串T中的位置为15（从0开始）。2暴力算法思路：循环T，从T的每个... 查看详情
kmp算法
...量，现在开始谈一下KMP算法了。kmp算法的思想是这样的：子串和长串比较，，当遇到相同的时候，继续比较，当不匹配时，子串右移，使得子串的不匹配位置的最长前缀串移动到长串的不匹配位置左边，与之相邻。之后继续，如... 查看详情
详细解读kmp模式匹配算法
...ei/article/details/52712461首先我们需要了解什么是模式匹配？子串定位运算又称为模式匹配（PatternMatching）或串匹配（StringMatching）。在串匹配中，一般将主串称为目标串，将子串称为模式串。本篇博客统一用S表示目标串，T表示模... 查看详情
字符串的模式匹配——brute-force算法和kmp算法
子串的定位操作是要在主串S中找出一个与子串T相同的子串，通常把主串S称为目标，把子串T称为模式把从目标S中查找模式为T的子串的过程称为“模式匹配”。1.Brute-Force算法的设计思想 Brute-Force是普通的模式匹配... 查看详情
常用算法3-字符串查找/模式匹配算法（bf&kmp算法）
...匹配算法！1.模式匹配什么是模式匹配呢？模式匹配，即子串P(模式串)在主串T(目标串)中的定位运算，也称串匹配假设我们有两个字符串：T(Targ 查看详情
kmp算法的next[]数组通俗解释
...符，加快匹配速度。当然我们可以看到这个算法针对的是子串有对称属性，如果有对称属性，那么就需要向前查找是否有可以再次匹配的内容。 在KMP算法中有个数组，叫做前缀数组，也有的叫next数组，每一个子串有一个固... 查看详情
扩展kmp算法
KMP算法中也涉及到子串与前缀的重复，而扩展KMP算法求得就是字符串S的所有后缀与字符串T的最长公共前缀可以知道，一个字符串所有的子串便是这个字符串所有后缀的所有前缀（或前缀的后缀)，那么求的信息其实也是字符串S... 查看详情
kmp算法(代码片段)
...够在线性时间内判定字符串(A[1-N])是否为字符串(B[1-M])的子串。对于刚刚接触KMP的同学来说，理解起来比较困难，难以理解(next[])数组的实际意义。当然你要硬背KMP也没人拦着你，因为代码确实就十几行但是其实并没有那么难懂，... 查看详情
模式匹配算法kmp
...符串str1和str2，现在要求查找str1中是否包含和str2相同的子串，如果存在，返回str1中子串的起始索引，如果没有，返回-1。2.暴力的解法比如str1为abcabcqwertystr2为abcq暴力解法为：首先，将str1和str2起始位置"对齐"abcabcqwertyabcq然后逐... 查看详情
算法导论————kmp
例题传送门：caioj1177KMP模版：子串是否出现【题意】有两个字符串SA和SB，SA是母串，SB是子串，问子串SB是否在母串SA中出现过。如果出现过输出第一次出现的起始位置和结束位置，否则输出"NO"【输入文件】第一行SA（1<=长度<... 查看详情
字符串匹配：字符串中查找某子串(代码片段)
字符串匹配：字符串中查找某子串需求具体算法常规方法程序KMP算法程序后续需求我们在平时的软件开发，尤其是嵌入式开发，字符串匹配是非常重要的一个算法。而目前常用的字符串匹配算法有很多，下面就来... 查看详情
kmp算法
...习串的匹配时，就是在目标串（主串）中找到与模式串（子串）一样的部分，返回它的子串位置的操作，这叫串的模式匹配。 一种效 查看详情
kmp算法详解以及java代码实现(代码片段)
...能。但是如果我们的需求是：一个已知字符串中查找子串，并且子串并不一定符合前缀匹配，那么此时Trie树就无能为力了。实际上这种字符串匹配的需求，在开发中非常常见，例如 查看详情
kmp算法详解——多图，多例子（c语言）(代码片段)
...f1f;2.1主串找字串2.2暴力求解3.KMP准备工作3.1字符串的前后子串3.2最大前后相等子串3.3最大前后相等子串练习4.KMP算法4.1简看KMP算法5Next数组 5.1j该回溯的位置 5.2学会计算Next数组 5.3用数学表示next数组（重点... 查看详情
字符串算法①——kmp
kmp算法是用来找A字符串的子串B的出现次数和位置的一种算法；在看后面之前先看一个链接https://kb.cnblogs.com/page/176818/然后对算法就有个大概的理解 为了实现这种算法我们需要一个next数组，也就是刚才链接里的部分匹配表，n... 查看详情
kmp算法详解以及java代码实现(代码片段)
...能。但是如果我们的需求是：一个已知字符串中查找子串，并且子串并不一定符合前缀匹配，那么此时Trie树就无能为力了。实际上这种字符串匹配的需求，在开发中非常常见，例如判断一个字符串是否包括某... 查看详情