kmp 最小循环节

kmp算法原理KMP算法（Knuth-Morris-Pratt算法）是一种用于快速搜索字符串中某个模式字符串出现位置的算法，由Knuth, Morris 和 Pratt于1977年提出。

KMP算法的工作方式如下：首先，给定一个主串S和一个模式串P，KMP算法的第一步就是先构造一个新的模式串P，其中的每一项存储着P中每一个字符前面由不同字符串组成的最长前缀和最长后缀相同的子串。

接着，在S中寻找P，它会从S的第一个字符开始，如果匹配上，就继续比较下一个字符，如果不匹配上，就根据P中相应位置上保存的信息跳到特定位置，接着再开始比较，如此不断循环下去，直到从S中找到P为止。

KMP算法的思路特别巧妙，比较效率很高，它的复杂度为O（m+n），其中m为主串的长度，n为模式串的长度。

它取代了以前的暴力搜索算法，极大地提高了程序的性能。

KMP算法的实现过程如下：（1）首先确定模式串P的每一个字符，构造模式串P的next数组：next[i]存储P中第i个字符之前最长相同前缀和后缀的长度（P中第i个字符之前最长相同前缀和后缀不包括第i个字符）；（2）接着从S中的第一个字符开始比较P中的每一个字符，如果字符不匹配，则采用next数组中保存的信息跳到特定位置，而不是暴力比较，以此不断循环，直到从S中找到P为止。

KMP算法是由Don Knuth, Vaughan Pratt和James Morris在1977年提出的。

它的思想是利用之前遍历过的P的信息，跳过暴力比较，可以把字符串搜索时间从O（m×n）降低到O（m+n）。

KMP算法在很多领域有着重要的应用，如文本编辑，模式匹配，编译器设计与多项式字符串匹配等等，都是不可或缺的。

KMP算法的详细解释什么是kmp算法呢？这是⼀个处理字符串的算法，⽤来判断给出的模式串p是否存在于⽂本串t中（p的长度⼩于t）。

在本⽂中，字符串储存在字符数组中，并且第⼀个字符放在下标为1的元素中。

那么如何理解kmp算法呢？⾸先要从最朴素的匹配算法说起。

我们判断p是否存在于t中，最原始的⽅法就是从头到尾⼀直遍历。

定义变量i为⽂本串t中的下标，定义变量j为模式串p中的下标，然后i表⽰看⽂本串的前i个字符，j表⽰判断这前i个字符组成的⼦串中，长度为j的前后缀是否相等。

如果t[i] = p[j]，则i与j同时后移⼀位，⽐较下⼀位是否相同，如果t[i] != p[j]，则表⽰串t在i位置处“失配”，需要重新进⾏匹配，i保持不动，并且j 必须返回到模式串p的开头，也就是相当于回退到1，然后再次进⾏循环。

如果t的长度为m，p的长度为n时，这样做的时间复杂度为O(m*n)kmp就是在这种最原始匹配算法的基础之上的改进算法。

Kmp的改进之处在哪⾥呢？上⾯这种复杂度最⼤的朴素⽅法中，有⼀个步骤，当“失配”时，我们的i不移动，但是j需要回到串p的开头，这样每⼀次失配，我们都需要再从模式串的开头重新开始匹配，相当于将j直接回退到1，然后再从1开始去试满⾜的最⼤的相同前后缀长度，多了好多次循环，聪明的科学家们想到的办法是：假设现在有这样⼀种情况：在遍历到⽂本串t的的前i-1个字符组成的⼦串之后，我们已经确定了该⼦串中的长度为j-1的前后缀是相同的，那么现在在考虑下⼀个字符（第a个）时发⽣失配，也就是第a个字符不等于第b个，我们不想让b直接回退到1，⽽是回退到1和b之间的某个值，以减⼩复杂度。

我们先放下这个问题，思考另外⼀个问题：如果要求⼀个字符串中相同的前缀和后缀的最长长度，怎么求呢？和上⾯的kmp其实特别像，还是分治的思想：假设我们现在已经看到了字符串的前i-1个元素，并且在这i-1个元素的⼦串中，长度为j-1的后缀和前缀是⼀样的，表⽰匹配到了j-1的长度，那么我们就可以考虑第字符串中第i个元素是否和第j个元素相同了，如果相同就继续匹配下去，如果不同，j仍要回退，但是不能把j直接回退到1然后递增地去判断，这样复杂度太⼤。

KMP算法以及优化（代码分析以及求解next数组和nextval数组）KMP算法以及优化(代码分析以及求解next数组和nextval数组)来了,数据结构及算法的内容来了,这才是我们的专攻,前⾯写的都是开胃⼩菜,本篇⽂章,侧重考研408⽅向,所以保证了你只要看懂了,题⼀定会做,难道这样思想还会不会么?如果只想看next数组以及nextval数组的求解可以直接跳到相应部分,思想总结的很⼲~~⽹上的next数组版本解惑先总结⼀下,⼀般KMP算法的next数组结果有两个版本,我们需要知道为什么会存在这种问题,其实就是前缀和后缀没有匹配的时候next数组为0还是为1,两个版本当然都是对的了,如果next数组为0是的版本,那么对于前缀和后缀的最⼤匹配长度只需要值+1就跟next数组是1的版本⼀样了,其实是因为他们的源代码不⼀样,或者对于模式串的第⼀个下标理解为0或者1,总之这个问题不⽤纠结,懂原理就⾏~~那么此处,我们假定前缀和后缀的最⼤匹配长度为0时,next数组值为1的版本,考研⼀般都是⽤这个版本(如果为0版本,所有的内容-1即可,如你算出next[5]=6,那么-1版本的next[5]就为5,反之亦然)~~其实上⾯的话总结就是⼀句话next[1]=0,j(模式串)数组的第⼀位下标为1,同时,前缀和后缀的最⼤匹配长度+1即为next数组的值,j所代表的的是序号的意思408反⼈类,⼀般数组第⼀位下标为1,关于书本上前⾯链表的学习⼤家就应该有⽬共睹了,书本上好多数组的第⼀位下标为了⽅便我们理解下标为1,想法这样我们更不好理解了,很反⼈类,所以这⾥给出next[1]=0,前缀和后缀的最⼤匹配长度+1的版本讲解前⾔以及问题引出我们先要知道,KMP算法是⽤于字符串匹配的~~例如:⼀个主串"abababcdef"我们想要知道在其中是否包括⼀个模式串"ababc"初代的解决⽅法是,朴素模式匹配算法,也就是我们主串和模式串对⽐,不同主串就往前移⼀位,从下⼀位开始再和模式串对⽐,每次只移动⼀位,这样会很慢,所以就有三位⼤神⼀起搞了个算法,也就是我们现在所称的KMP算法~~代码以及理解源码这⾥给出~~int Index_KMP(SString S,SString T,intt next[]){int i = 1,j = 1;//数组第⼀位下标为1while (i <= S.length && j <= T.length){if (j == 0 || S.ch[i] == T.ch[j]){//数组第⼀位下标为1,0的意思为数组第⼀位的前⾯,此时++1,则指向数组的第⼀位元素++i;++j; //继续⽐较后继字符}elsej = next[j]; //模式串向右移动到第⼏个下标,序号(第⼀位从1开始)}if (j > T.length)return i - T.length; //匹配成功elsereturn 0;}接下来就可以跟我来理解这个代码~~还不会做动图,这⾥就⼿画了~~以上是⼀般情况,那么如何理解j=next[1]=0的时候呢?是的,这就是代码的思路,那么这时我们就知道,核⼼就是要求next数组各个的值,对吧,⼀般也就是考我们next数组的值为多少~~next数组的求解这⾥先需要给出概念,串的前缀以及串的后缀~~串的前缀:包含第⼀个字符,且不包含最后⼀个字符的⼦串串的后缀:包含最后⼀个字符,且不包含第⼀个字符的⼦串当第j个字符匹配失败,由前1~j-1个字符组成的串记为S,则:next[j]=S的最长相等前后缀长度+1与此同时,next[1]=0如,模式串"ababaa"序号J123456模式串a b a b a anext[j]0当第六个字符串匹配失败,那么我们需要在前5个字符组成的串S"ababa"中找最长相等的前后缀长度为多少再+1~~如串S的前缀可以为:"a","ab","aba","abab",前缀只不包括最后⼀位都可串S的后缀可以为:"a","ba","aba","baba",后缀只不包括第⼀位都可所以这⾥最⼤匹配串就是"aba"长度为3,那么我们+1,取4序号J123456模式串a b a b a anext[j]04再⽐如,当第⼆个字符串匹配失败,由前1个字符组成的串S"a"中,我们知道前缀应当没有,后缀应当没有,所以最⼤匹配串应该为0,那么+1就是取1~~其实这⾥我们就能知道⼀个规律了,next[1]⼀定为0(源码所造成),next[2]⼀定为1(必定没有最⼤匹配串造成)~~序号J123456模式串a b a b a anext[j]014再再⽐如,第三个字符串匹配失败,由前两个字符组成的串S"ab"中找最长相等的前后缀长度,之后再+1~~前缀:"a"后缀:"b"所以所以这⾥最⼤匹配串也是没有的长度为0,那么我们+1,取1序号J123456模式串a b a b a anext[j]0114接下来你可以⾃⼰练练4和5的情况~~next[j]011234是不是很简单呢?⾄此,next数组的求法以及kmp代码的理解就ok了~~那么接下来,在了解以上之后,我们想⼀想KMP算法存在的问题~~KMP算法存在的问题如下主串:"abcababaa"模式串:"ababaa"例如这个问题我们很容易能求出next数组序号J123456模式串a b a b a anext[j]011234此时我们是第三个字符串匹配失败,所以我们的next[3]=1,也就是下次就是第⼀个字符"a"和主串中第三个字符"c"对⽐,可是我们刚开始的时候就已经知道模式串的第三个字符"a"和"c"不匹配,那么这⾥不就多了⼀步⽆意义的匹配了么?所以我们就会有kmp算法的⼀个优化了~~KMP算法的优化我们知道,模式串第三个字符"a"不和主串第三个字符"c"不匹配,next数组需要我们的next[3]=1,也就是下次就是第⼀个字符"a"和主串中第三个字符"c"对⽐,之后就是模式串第⼀个字符"a"不和"c"匹配,就是需要变为next[1]=0,那么我们要省去步骤,不就可以直接让next[3]=0么?序号J12345模式串a b a b anext[j]01123nextval[j]00那么怎么省去多余的步骤呢?这就是nextval数组的求法~~nextval的求法以及代码理解先贴出代码for (int j = 2;j <= T.length;j++){if (T.ch[next[j]] == T.ch[j])nextval[j] = nextval[next[j]];elsenextval[j] = next[j];}如序号J123456模式串a b a b a anext[j]011234nextval[j]0⾸先,第⼀次for循环,j=2,当前序号b的next[2]为1,即第⼀个序号所指向的字符a,a!=当前序号b,所以nextval[2]保持不变等于next[2]=1序号J123456模式串a b a b a anext[j]011234nextval[j]01第⼆次for循环,j=3,当前序号a的next[3]为1,即第⼀个序号所指向的字符a,a=当前序号a,所以nextval[3]等于nextval[1]=0序号J123456模式串a b a b a anext[j]011234nextval[j]010第三次for循环,j=4,当前序号b的next[4]为2,即第⼆个序号所指向的字符b,b=当前序号b,所以nextval[4]等于nextval[2]=1序号J123456模式串a b a b a anext[j]011234nextval[j]0101就是这样,你可以练练5和6,这⾥直接给出~~序号J123456模式串a b a b a anext[j]011234nextval[j]010104⾄此nextval数组的求法你也应该会了,那么考研要是考了,那么是不是就等于送分给你呢?⼩练习那么你试着来求⼀下这个模式串的next和nextval数组吧~~next[j]nextval[j]⼩练习的答案序号j12345模式串a a a a b next[j]01234 nextval[j]00004。

kmp算法概念KMP算法概念KMP算法是一种字符串匹配算法，它的全称是Knuth-Morris-Pratt 算法。

该算法通过预处理模式串，使得在匹配过程中避免重复比较已经比较过的字符，从而提高了匹配效率。

一、基本思想KMP算法的基本思想是：当模式串与文本串不匹配时，不需要回溯到文本串中已经比较过的位置重新开始匹配，而是利用已知信息跳过这些位置继续匹配。

这个已知信息就是模式串自身的特点。

二、next数组1.定义next数组是KMP算法中最核心的概念之一。

它表示在模式串中当前字符之前的子串中，有多大长度的相同前缀后缀。

2.求解方法通过观察模式串可以发现，在每个位置上出现了相同前缀和后缀。

例如，在模式串“ABCDABD”中，第一个字符“A”没有任何前缀和后缀；第二个字符“B”的前缀为空，后缀为“A”；第三个字符“C”的前缀为“AB”，后缀为“B”；第四个字符“D”的前缀为“ABC”，后缀为“AB”；第五个字符“A”的前缀为“ABCD”，后缀为“ABC”；第六个字符“B”的前缀为“ABCDA”，后缀为“ABCD”；第七个字符“D”的前缀为“ABCDAB”，后缀为“ABCDA”。

根据上述观察结果，可以得到一个求解next数组的方法：（1）next[0]=-1，next[1]=0。

（2）对于i=2,3,...,m-1，求解next[i]。

①如果p[j]=p[next[j]]，则next[i]=next[j]+1。

②如果p[j]≠p[next[j]]，则令j=next[j]，继续比较p[i]和p[j]。

③重复执行步骤①和步骤②，直到找到满足条件的j或者j=-1。

（3）通过上述方法求解出所有的next值。

三、匹配过程在匹配过程中，文本串从左往右依次与模式串进行比较。

如果当前字符匹配成功，那么继续比较下一个字符；否则利用已知信息跳过一些位置继续进行匹配。

具体地：（1）如果当前字符匹配成功，则i和j都加1。

（2）如果当前字符匹配失败，则令j=next[j]。

KMP算法的时间复杂度KMP算法是一种字符串匹配算法，它可以在一个主串中高效地查找所有匹配某个模式串的位置。

在计算机科学中，算法的时间复杂度是衡量算法执行时间与输入规模之间关系的度量。

在本文中，我们将深入探讨KMP算法的时间复杂度。

KMP算法的时间复杂度可通过三个方面来分析：预处理阶段的时间复杂度、匹配阶段的时间复杂度以及总体时间复杂度。

1. 预处理阶段的时间复杂度在KMP算法中，要先对模式串进行预处理，生成部分匹配表（Partial Match Table），也称为最长公共前后缀表（Longest Proper Prefix which is also Sufix，简称为LPS表）。

这个过程的时间复杂度是O(m)，其中m是模式串的长度。

在生成部分匹配表的过程中，KMP算法利用了前缀与后缀的性质，通过动态规划的方式计算每个位置的最长匹配长度。

虽然这个过程需要遍历整个模式串，但是每次计算的操作都具有重叠子问题的性质，因此可以通过状态转移方程高效地计算出来。

2. 匹配阶段的时间复杂度在匹配阶段，KMP算法将主串与模式串进行逐个字符的比较，并利用已经生成的部分匹配表来决定下一次比较的位置。

这个过程的时间复杂度是O(n)，其中n是主串的长度。

在匹配过程中，KMP算法利用了部分匹配表的信息，根据当前位置的匹配长度来确定下一次比较的位置。

通过避免无效的比较，KMP 算法可以在最坏情况下实现线性的时间复杂度。

3. 总体时间复杂度KMP算法的总体时间复杂度是预处理阶段的时间复杂度与匹配阶段的时间复杂度之和。

即O(m) + O(n) = O(m + n)。

从总体时间复杂度可以看出，KMP算法的执行时间与主串和模式串的长度之和成正比。

相比于朴素的字符串匹配算法，KMP算法可以大大提高匹配的效率，尤其是在模式串较长的情况下。

总结：KMP算法的时间复杂度是O(m + n)，其中m是模式串的长度，n是主串的长度。

通过对模式串进行预处理并利用部分匹配表的信息，KMP算法可以高效地在主串中查找所有匹配模式串的位置。

KMP算法简介什么是KMP算法KMP算法（Knuth-Morris-Pratt算法）是一种用于字符串匹配的算法，用于在一个主串中查找一个模式串的出现位置。

它的特点是在匹配失败时，不回溯主串的指针，而是通过利用已经匹配过的信息，将模式串尽量地向后移动，从而提高匹配效率。

KMP算法的原理KMP算法的核心思想是利用模式串自身的特点，通过预处理模式串，构建一个部分匹配表（Partial Match Table），从而在匹配过程中可以根据已匹配的信息来决定下一步的匹配位置。

部分匹配表部分匹配表是一个与模式串对应的数组，用于存储模式串在每个位置上的最长相同前缀后缀的长度。

例如，对于模式串”ABCDABD”，其部分匹配表为：位置部分匹配值0 01 02 03 04 15 26 0KMP算法的匹配过程KMP算法的匹配过程可以简述为以下几个步骤：1.预处理模式串，构建部分匹配表；2.在主串中从左到右逐个字符进行匹配；3.如果当前字符匹配成功，则继续比较下一个字符；4.如果当前字符匹配失败，则根据部分匹配表，将模式串向右移动一定的距离，再次进行匹配；5.重复步骤3和4，直到模式串匹配完毕或者主串匹配完毕。

KMP算法的优势相较于朴素的字符串匹配算法，KMP算法具有以下优势：1.减少了不必要的字符比较次数，提高了匹配效率；2.通过预处理模式串，可以在匹配过程中根据已匹配的信息决定下一步的匹配位置，避免了回溯主串的指针。

KMP算法的应用KMP算法在字符串匹配中有着广泛的应用，例如：1.字符串查找：在一个文本中查找一个子串的出现位置；2.字符串替换：将一个文本中的某个子串替换为另一个字符串；3.DNA序列匹配：在生物信息学中，用于比对DNA序列的相似性。

KMP算法的压力测试为了验证KMP算法的效率和稳定性，我们进行了一系列的压力测试。

测试环境•操作系统：Windows 10•处理器：****************************•内存：16GB测试方法我们使用不同长度的主串和模式串进行匹配，记录下KMP算法的执行时间，并与朴素的字符串匹配算法进行对比。

深度剖析KMP,让你认识真正的NextKMP算法，想必大家都不陌生，它是求串匹配问题的一个经典算法（当然如果你要理解成放电影的KMP，请退出本页面直接登录各大电影网站，谢谢），我想很多人对它的理解仅限于此，知道KMP能经过预处理然后实现O(N*M）的效率，比brute force（暴力算法）更优秀等等，其实KMP算法中的Next函数，功能十分强大，其能力绝对不仅仅限于模式串匹配，它并不是KMP的附属品,其实它还有更多不为人知的神秘功能^_^先来看一个Next函数的典型应用，也就是模式串匹配，这个相信大家都很熟悉了:POJ 3461 Oulipo——很典型的模式串匹配问题，求模式串在目标串中出现的次数。

#include<cstdio>#include<iostream>#include<cmath>#include<cstring>#include<algorithm>using namespace std;#define MAX 1000001char t[MAX];char s[MAX];int next[MAX];inline void calnext(char s[],int next[]){int i;int j;int len=strlen(s);next[0]=-1;j=-1;for(i=1;i<len;i++){while(j>=0&&s[i]!=s[j+1])j=next[j];if(s[j+1]==s[i])//上一个循环可能因为j=-1而不做，此时不能知道s[i]与s[j+1]的关系。

故此需要此条件。

j++;next[i]=j;}}int KMP(char t[],char s[]){int ans=0;int lent=strlen(t);int lens=strlen(s);if(lent<lens)return 0;int i,j;j=-1;for(i=0;i<lent;i++){while(j>=0&&s[j+1]!=t[i])j=next[j];if(s[j+1]==t[i])j++;if(j==lens-1){ans++;j=next[j];}}return ans;}int main(){int testcase;scanf("%d",&testcase);int i;for(i=1;i<=testcase;i++){scanf("%s%s",s,t);calnext(s,next);printf("%d\n",KMP(t,s));}return 0;}—————————————————————————————————————————————POJ 2406 Power Strings这道题就比较有意思了，乍看之下，怎么看貌似都与KMP无关，呵呵，这就是因为你没有深入理解Next 的含义；我首先来解释下这道题的题意，给你一个长度为n的字符串，首先我们找到这样一个字符串，这个字符串满足长度为n的字符串是由这个字符串重复叠加得到并且这个字符串的长度要最小.，然后输出重复的次数。

KMP算法详解(C++版)KMP算法是一种字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）.KMP 算法之所以难懂，很大一部分原因是很多实现的方法在一些细节的差异。

然后去看另外的方法，就全都乱了！体现在几个方面： next 数组，有的叫做“失配函数”，其实是一个东西； next 数组中，有的是以下标为 0 开始的，有的是以 1 开始的； KMP 主算法中，当发生失配时，取的 next数组的值也不一样！就这样，各说各的，乱的很！所以，在阐述我的理解之前，我有必要说明一下，我是用 next 数组的， next 数组是以下标 0 开始的！还有，我不会在一些基础的概念上浪费太多，所以你在看这篇文章时必须要懂得一些基本的概念，例如“朴素字符串匹配”“前缀”，“后缀”等！假设在我们的匹配过程中出现了这一种情况：根据 KMP 算法，在该失配位会调用该位的 next 数组的值！在这里有必要来说一下 next 数组的作用！说的太繁琐怕你听不懂，让我用一句话来说明：返回失配位之前的最长公共前后缀！好，不管你懂不懂这句话，我下面的文字和图应该会让你懂这句话的意思以及作用的！首先，我们取之前已经匹配的部分（即蓝色的那部分！）我们在上面说到 next 数组的作用时，说到“最长公共前后缀”，体现到图中就是这个样子！接下来，就是最重要的了！没错，这个就是 next 数组的作用了 :返回当前的最长公共前后缀长度，假设为 len 。

因为数组是由 0 开始的，所以 next 数组让第 len位与主串匹配就是拿最长前缀之后的第 1 位与失配位重新匹配，避免匹配串从头开始！如下图所示！（重新匹配刚才的失配位！）如果都说成这样你都不明白，那么你真的得重新理解什么是 KMP 算法了！接下来最重要的，也是 KMP 算法的核心所在，就是 next 数组的求解！不过，在这里我找到了一个全新的理解方法！如果你懂的上面我写的的，那么下面的内容你只需稍微思考一下就行了！跟刚才一样，我用一句话来阐述一下 next 数组的求解方法，其实也就是两个字：继承a 、当前面字符的前一个字符的对称程度为 0 的时候，只要将当前字符与子串第一个字符进行比较。

字符串匹配方法引言：字符串匹配是计算机科学中一项重要的技术，它在文本处理、数据分析、搜索引擎等领域都有广泛的应用。

本文将介绍几种常见的字符串匹配方法，包括暴力匹配、KMP算法、Boyer-Moore算法和正则表达式。

一、暴力匹配算法暴力匹配算法，也称为朴素匹配算法，是最简单直观的字符串匹配方法。

它的思想是从待匹配文本的第一个字符开始，依次与模式串进行比较，若匹配失败则移动到下一个字符继续比较，直到找到匹配的子串或者遍历完整个文本。

该算法的时间复杂度为O(n*m)，其中n为文本长度，m为模式串长度。

二、KMP算法KMP算法是一种高效的字符串匹配算法，它的核心思想是通过预处理模式串，构建一个部分匹配表（Next数组），以便在匹配过程中根据已匹配的前缀字符来确定下一次匹配的位置。

这样可以避免不必要的回溯，提高匹配效率。

KMP算法的时间复杂度为O(n+m)，其中n为文本长度，m为模式串长度。

三、Boyer-Moore算法Boyer-Moore算法是一种基于比较字符的右移策略的字符串匹配算法。

它的主要思想是从模式串的末尾开始与待匹配文本比较，若匹配失败则根据预先计算好的字符移动表来决定模式串的右移位数。

这样可以根据比较结果快速确定下一次比较的位置，从而提高匹配效率。

Boyer-Moore算法的时间复杂度为O(n/m)，其中n为文本长度，m为模式串长度。

四、正则表达式正则表达式是一种强大的字符串匹配工具，它通过一种特定的语法规则来描述字符串的模式，并通过匹配模式来判断字符串是否符合要求。

正则表达式可以实现复杂的匹配功能，包括字符匹配、重复匹配、分组匹配等。

在文本处理、数据清洗、搜索引擎等领域都有广泛的应用。

结论：字符串匹配是计算机科学中一项重要的技术，不同的匹配方法适用于不同的应用场景。

暴力匹配算法简单直观，适用于模式串较短的情况；KMP算法通过预处理模式串，提高匹配效率；Boyer-Moore算法通过右移策略，减少不必要的比较次数；正则表达式可以实现复杂的匹配功能。

（原创）详解KMP算法KMP算法应该是每⼀本《数据结构》书都会讲的，算是知名度最⾼的算法之⼀了，但很可惜，我⼤⼆那年压根就没看懂过~~~之后也在很多地⽅也都经常看到讲解KMP算法的⽂章，看久了好像也知道是怎么⼀回事，但总感觉有些地⽅⾃⼰还是没有完全懂明⽩。

这两天花了点时间总结⼀下，有点⼩体会，我希望可以通过我⾃⼰的语⾔来把这个算法的⼀些细节梳理清楚，也算是考验⼀下⾃⼰有真正理解这个算法。

什么是KMP算法：KMP是三位⼤⽜：D.E.Knuth、J.H.Morris和V.R.Pratt同时发现的。

其中第⼀位就是《计算机程序设计艺术》的作者！！KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。

说简单点就是我们平时常说的关键字搜索。

模式串就是关键字（接下来称它为P），如果它在⼀个主串（接下来称为T）中出现，就返回它的具体位置，否则返回-1（常⽤⼿段）。

⾸先，对于这个问题有⼀个很单纯的想法：从左到右⼀个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动⼀位。

这有什么难的？我们可以这样初始化：之后我们只需要⽐较i指针指向的字符和j指针指向的字符是否⼀致。

如果⼀致就都向后移动，如果不⼀致，如下图：A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后⼜重新开始这个步骤：基于这个想法我们可以得到以下的程序：1/**23 * 暴⼒破解法45 * @param ts 主串67 * @param ps 模式串89 * @return如果找到，返回在主串中第⼀个字符出现的下标，否则为-11011*/1213public static int bf(String ts, String ps) {1415char[] t = ts.toCharArray();1617char[] p = ps.toCharArray();1819int i = 0; // 主串的位置2021int j = 0; // 模式串的位置2223while (i < t.length && j < p.length) {2425if (t[i] == p[j]) { // 当两个字符相同，就⽐较下⼀个2627 i++;2829 j++;3031 } else {3233 i = i - j + 1; // ⼀旦不匹配，i后退3435 j = 0; // j归03637 }3839 }4041if (j == p.length) {4243return i - j;4445 } else {4647return -1;4849 }5051 }上⾯的程序是没有问题的，但不够好！（想起我⾼中时候数字⽼师的⼀句话：我不能说你错，只能说你不对~~~）如果是⼈为来寻找的话，肯定不会再把i移动回第1位，因为主串匹配失败的位置前⾯除了第⼀个A之外再也没有A了，我们为什么能知道主串前⾯只有⼀个A？因为我们已经知道前⾯三个字符都是匹配的！（这很重要）。