⑴ 算法-KMP
大一下参加学校ACM预备队集训的时候首次接触KMP算法，当时看了很多介绍文章，仍然不是很理解其实质，只是简单地套模板AC题目，待大二数据结构与算法课堂上再听老师介绍一次，才恍然大悟其实KMP也就是那么回事嘛。但当初为啥看那么多文章都没弄明白呢？正巧最近和朋友聊天时他告诉我他对KMP不是很理解，于是打算自己写一篇文章，巩固自己对KMP的认识，也希望能够帮助更多朋友理解KMP。
在开始之前，需要知晓的概念：
前缀：以原串串头为自身串头的子串，如 的前缀有：
后缀：以原串串尾为自身串尾的子串，如 的后缀有：
注意：字符串前后缀都不包括该串本身
给你一个文本串T(Text String)
再给你一个模式串P(Pattern String)
问该模式串是否在文本串中，怎么找？
一开始只好分别从文本串与模式串的串头开始逐字母比较
二者相同，再比较T串与P串的下一位
如此反复
如果一直这么顺利，两串对应位置的字符总相同，待P串中最后一个字符也匹配完毕，说明该模式串在文本串中存在，耶( •̀ ω •́ )y超开心，查找结束。但，大多数匹配过程不会如此顺利，在该例中，当匹配进行至
很明显，失配了。现在怎么办？按朴素思想，将P串相对T串整体右移一位，重新开始匹配，即
但这种算法效率无疑是十分低下的。设T串长度N，P串长度M，则朴素算法时间复杂度为O(MN)
已知的重要信息并没有被使用——已匹配的字符串前缀
在上例中，当P串最后一个字符匹配失败时，其已有包含七个字符的 前缀子串S 匹配成功
完全可以利用前缀子串S做点什么。观察到在S串
中，有相同前后缀，即下图蓝色部分
而S串各字符又与T串中对应字符相同，即有
当失配发生后，直接将P串右移四位使S串蓝色后缀部分对齐T串中蓝色前缀部分
从图中红框部分继续尝试匹配，发现再次失配。这次，已匹配成功的前缀串S为
而在该串中没有相同的前后缀，只能将P串串头移至失配处进行比较
再次失配。此时前缀串S为空串，只好如朴素算法般将P串整体右移一位，重新开始比较
匹配成功。于是又按照之前的步骤往下匹配，直至再次失配或匹配成功
后续步骤同上，不再赘述
上述示例已展现，KMP算法的精髓在于对已匹配成功的前缀串S的利用
在朴素算法中，匹配失败了，T串待匹配字符会回溯
T串原本已匹配至T[7] = 'X'，但是因为失配，需回溯到T[1] = 'b'重新开始匹配
而在KMP算法中，若P[M]与T[K]匹配失败，K不会回溯。既然匹配过程是从T[0]开始逐渐向右进行的，至T[K]失配发生时，T[0]至T[K-1]早已匹配过，何必再回溯过去重复匹配呢？于是乎，就如问题引入部分展示般
每当失配发生，我们总是去关注P串中已匹配成功的前缀串S
因为该前缀串是匹配成功的，说明在T串中必定存在与该前缀串相同的子串，记为S'
若S串中存在相同前后缀
则S'串必然也存在此相同前后缀
所以只需将P串右移四位，使得S串的该相同前缀对齐S'串的该相同后缀
再尝试比较T[7]与P[3]
至于T[7]与P[3]是否能够匹配另说（当然，本例中一看就知道没匹配上），但通过对前缀串S的利用，成功省去了P串右移一位、两位和三位后的无效匹配
继续深入思考，给定一个具体的P串，其第N位的前缀串S内容是固定的，则S是否存在相同前后缀、相同前后缀的长度与内容也是确定的。换言之，对于一个具体的P串，当其与给定T串匹配至P[N]失配，P串应右移几位再次与T串进行匹配也是确定的。我们完全可以使用一个数组记录当P[N]失配后，应当使用N之前的哪一位再来与T串进行匹配，以此提高匹配效率，记该数组为Next数组
定义Next[i] = j表示当P串中第i位失配后，跳转至P串第j位再次尝试匹配
还是以之前的P串为例，它的Next数组求出来应为
取下标5为例，其前缀串为
最长相同前后缀为
若P[5]失配，应跳转至P[1]再次尝试匹配（最长相同前缀对应P[0]，则取其后一位P[1]，若存在多位，则取最后一位的下一位），P[5]的前一个字符P[4]对应字符'a'，而P[1]前一个字符P[0]同对应字符'a'，保证了P[1]之前字符与T串中对应字符保持匹配。所以Next[5] = 1，其余下标对应Next数组值同如此求。
特别地，规定Next[0] = -1。而对于除下标0外的任意下标N，Next[N]的含义是 前N-1个已匹配成功的字符构成的前缀串S中，最长相同前后缀长度。 所以若在下标为N处匹配失败了，则应前往Next[N]所对应的下标处匹配。
具体地，以下图所示为例，P[6]与T[6]失配
而Next[6] = 2，所以使用P[2]再次尝试与T[6]进行匹配
当求出P串Next数组后，便可快速进行与T串的匹配
现在问题只剩下如何求Next数组，注意到Next数组既然只与P串本身相关，与文本串T无关，故令P串与自身匹配即可求得
考虑字符串
其Next数组应为
令其与给定文本串相匹配
当匹配进行至
失配，于是跳转至P[Next[3]] = P[1]处再次尝试匹配
再度失配，也必然失配
问题在于不该出现P[N] =P[Next[N]]
若P[N] =P[Next[N]]，则P[N]失配后使用P[Next[N]]再次尝试匹配，由于P[N] =P[Next[N]]，P[N]匹配失败，P[Next[N]]必然也失败
因此，若出现P[N] =P[Next[N]]情况，则令Next[N]=Next[Next[N]]
本例中该字符串新Next数组为
当匹配进行至
失配，于是跳转至P[Next[3]] = P[0]处再次尝试匹配
省去了之前跳转至P[1]处的无效匹配
设T串长度M，P串长度N，由于KMP算法不会回溯，分析易知时间复杂度为O(m+n)
对于P[N]，若其前缀串S含相同前后缀F，且F长度为n（n>1），Next[N]可以取1至n中任意值，为最大化匹配效率考虑，总是取最大相同前后缀以提高效率，节省时间
⑵ 数据结构-串的模式匹配
串的模式匹配就是子串定位操作。给定两明亏个串s="s0 s1 ... s(n-1)"和t="t0 t1 ... t(m-1)"（其中n和m分别是串s和t的长度），在主串s中寻找子串t的过程称为模式匹配，t称为模式。如果在s中找到等于t的子串，则称匹配成功，返回t在s中的首次出现的下标位置；否则匹配失败，返回-1。
本文介绍三个串模式匹配算法，分别是简单回溯算法（Brute-Force，BF算法）、KMP算法、KMP算法的改进。
从主串s的第0个字符开始，与模式串t的第0个字符开始逐字符比较，不相同时回溯到模式串t的第0个和主串s的第1个字符，重新开始比较。以此类推，直到t的所有字符完成匹配，则匹配成功，否则匹配失败。
BF算法速度慢的原因是存在大量不必要的回溯，即在某一趟与t的匹配过程失败后，需要返回s串开始字符的下一字符重新开始比较，这对于某些模式串t来说是不必要的。例如，若s=12123123132，t=12313，在t与12 12312 3132中加粗子序列进行比较时，在 2 处发生失配，BF算法接下来将t与121 23123 132、1212 31231 32、12123 12313 2比较。由于t中的231、312与其开始的123并不相同，显然t与121 23123 132、1212 31231 32的比较是不必要的。
KMP算法就是利用模式串中与模式串开头部分子串的重复性来减少重复回溯，实现新一轮比较的直接跳转。 具体来说，KMP算法利用一个数组记录模式串中每一个字符前面有几个字符与模式串从头重复，在与s串比较失配时，直接跳转到重复子串的下一个字符继续比较，而不用跳转至模式串t的第0个字符。
算法步骤： ①计算跳转数组next。②利用KMP算法进行模式匹配。
next数组通过递推计算，即如果当前字符 t[j] 的前一个字符 t[j-1] 与其 next[j-1] 指向的字符 t[next[j-1]] 相同，意味着 t[j] 前的 next[j-1]+1 个字符与从 t[0] 到 t[next[j-1]] 的子串相同，因此 next[j]=next[j-1]+1 ；如果不相同，则递推至 t[next[j-1]] 的next值指向的字符，与 t[j-1] 比较，直到确认 t[j] 前与 t 串从头重复的数羡字符数，或者无重复字符标记为薯槐拍 0 。
注意此处的函数返回参数类型为int*，用于 返回一位数组 ，且返回的这个一位数组必须在函数中用static定义。
KMP算法进行模式匹配时，只需在回溯时将 j 指针赋值为 next[j] 。需要注意的是，若 next[j] 为 -1 ，则意味着 t[j] 前面没有与 t 从头重复的字符，且 t[j] 与 s[i] 失配，则 i 和 j 均加 1 。
考虑更特殊的模式串，还能进一步减少不必要的回溯次数。例如，s=111211112，t=11112，按照上述next的计算方式，next={-1,0,1,2,3}。当 i=3, j=3 时失配，此时 s[i]=2, t[j]=1 ，由于 next[j]=2 ，于是 j 跳转为 2 ，t=11 1 12与s=111 2 11112比较。由于 t[next[j]]=t[j] 也为 1 ，必然与 s[i]=2 不相同，显然这次回溯也不必要。
总结来说， 当失配的字符与待跳转的字符相同时，跳转一步并无意义，可再跳一步 ，即将当前字符置为跳转后字符的next值。
⑶ 数据结构 5.7 KMP算法匹配过程
void get_nextval(char T[] int next[]){ //求模式串T的next函数值凳此并存入数组next j = ; next[ ] = ; k = ; while ( T[j+ ] != ) { if (k = = || T[j] = = T[k]) { ++j; ++k;羡粗山 if (T[j]!=T[k]) next[j] = k; else next[j] = next[k]; }//if else k = next[k]; }// while兄中}//get_nextval
KMP算法匹配的过程动画演示
lishixin/Article/program/sjjg/201311/23526
⑷ kmp算法详解
KMP模式匹配算法
KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的明[4]。
求得模式的特征向量之后，基于特征分析的快速模式匹配算法(KMP模式匹配算法)与朴素匹配算法类似，只是在每次匹配过程中发生某次失配时，不再单纯地把模式后移一位，而是根据当前字符的特征数来决定模式右移的位数[3]。
include "string. h"
#include<assert. h>
int KMPStrMatching(String T, String P, int. N, int startIndex)
{int lastIndex=T.strlen() -P.strlen();
if((1 astIndex- startIndex)<0)//若 startIndex过大,则无法匹配成功
return (-1);//指向P内部字符的游标
int i;//指向T内部字符的游标
int j=0;//指向P内部字符的游标
for(i= startIndex; i <T.strlen(); i++)
{while(P[j]!=T[i]&& j>0)
j=N[j-1];
if(P[j]==T[i])
j++;
if(j ==P.strlen())
return(1-j+1);//匹配成功,返回该T子串的开始位置
}
return (-1);
}
⑸ kmpe算法详解
KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I"m matrix67"，字符串B="matrix"，我们就说B是A的子串。
解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多“最坏情况”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设 m<=n），即传说中的KMP算法。
望采纳 谢谢
⑹ 算法基础 - 朴素模式匹配算法、KMP模式匹配算法
假设我们要从 主字符串goodgoogle 中匹配 子字符串google
朴素模式匹配算法就是 通过从主字符的头部开始 一次循环匹配的字符串的挨个字符 如果不通过 则主字符串头部位置遍历位置+1 在依次遍历子字符串的字符
匹配过程
主字符串从第一位开始 取出g 子字符串取出第一位 g 匹配 进入子循环
取出o 取出o 匹配
取出o 取出o 匹配
取出d 取出g 不匹配 主字符串遍历位置+1
主字符串从第二位开始 取出o 子字符串取出第一位 g 不匹配 主字符串遍历位置+1
主字符串从第三位开始 取出o 子字符串取出第一位 g 不匹配 主字符串遍历位置+1
主字符串从第四位开始 取出d 子字符串取出第一位 g 不匹配 主字符串遍历位置+1
主字符串从第五位开始 取出g 子字符串取出第一位 g 匹配 进入子循环
取出o 取出o 匹配
取出o 取出o 匹配
取出g 取出g 匹配
取出l 取出l 匹配
取出e 取出e 匹配 子循环结束 匹配成功
假设主字符串 长度为 n 子字符串长度为m n>= m
最好的情况需要匹配m次 时间复杂度为 0(m)
例如 000000000001 匹配 00001 每次进入子循环之后 都要遍历到最后一次子循环才得出不匹配
需要匹配次数 (n-m+1) * m
最坏的情况需要匹配m次 时间复杂度为 0((n-m+1) * m)
KMP 算法的主要核心就是 子字符串在子循环内得出不匹配时 主字符串当前的判断位不需要回溯–也就是不可以变小 ，且子循环的判断位需要回溯 回溯位与子字符串本身是否具有重复结构有关 。 以此来规避无效的判断
时间复杂度为 O(n+m)
如果主串 S = "abcdefgab" 我们要匹配的子串 T = "abcdex" 如果用前面的朴素算法 ， 前5个字母完全相同
直到第6个字母 f 和 x 不同
步骤1
S: a b c d e f g a b
T: a b c d e x
接下来如果用朴素算法的话 那么应该是如下比较
步骤2
S: a b c d e f g a b
T: # a b c d e x
b 和 a 不匹配
步骤3
S: a b c d e f g a b
T: # # a b c d e x
a和c 不匹配
步骤4
S: a b c d e f g a b
T: # # # # a b c d e x
d和a 不匹配
步骤5
S: a b c d e f g a b
T: # # # # a b c d e x
a和e 不匹配
步骤6
S: a b c d e f g a b
T: # # # # # a b c d e x
即主串S中的第2 ，3 ， 4， 5， 6 位都与子串T的首字符不相等
对于子串T来说 如果首字符a与后面的bcdex中任意一个字符都不相等
那么对于上面的第一步来说 前五位都相等 那么 可以得到 子串首字符a 与主串的第2，3，4，5 位都不相等
即步骤2 ， 3 ，4 ，5 都是多余的 可以直接进入步骤6
如果子串的首字符串与后面的字符有相等的情况
假设S = "abcababca" T= "abcabx"
朴素算法
步骤1
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配
步骤2
S: a b c a b a b c a
T: # a b c a b x
b 与 a 不匹配
步骤3
S: a b c a b a b c a
T: # # a b c a b x
c 与 a 不匹配
步骤4
S: a b c a b a b c a
T: # # # a b c a b x
a 与 a 匹配
步骤5
S: a b c a b a b c a
T: # # # # a b c a b x
b 与 b 匹配
步骤6
S: a b c a b a b c a
T: # # # # a b c a b x
a 与 c 不匹配
因为步骤1 中已经得出 前五位已经完全匹配 并且子串首字符ab 存在相同的情况 所以 步骤2，3 是多余的
直接进入步骤4 因为步骤1中已经得出 主串与子串前五位相同 同时 子串1 2 位与 子串的4 5 位相同 所以可得出
子串1 2 位 与当前主串匹配位置开始的前两位也就是主串的4 5 位匹配 所以步骤4 , 5 是多余的 可以直接进入步骤6
通过上面的两个例子我们可以发现 主串的比较位是不会回溯的 ， 而子串的比较位与子串本身结构中是否有重复相关
子串不重复 举例
S: a b c d e f g a
T: a b c d e x
子串第6位不匹配 且本身没有重复 那么下一次循环 就变成了 子串的第一位与主串的第二位比较
即子串的匹配位从6 变成了1
S: a b c d e f g a
T: # a b c d e x
子串重复 举例
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配
子串在第六位发生不匹配是 前五位abcab 具有重复结构 ab 所以子串匹配位发生变化 即子串的匹配位从6 变成了 3
S: a b c a b a b c a
T: # # # a b c a b x
a 与 c 不匹配
我们可以得出 子串匹配位的值 与主串无关 只取决于当前字符串之前的串前后缀的相似度
也就是说 我们在查找字符前 ，要先对子串做一个分析 获取各个位置不匹配时 下一步子串的匹配位
前缀 ： 从头开始数 不包含最后一位
后缀 : 不是倒着数 是以和前缀相同的字符串为结尾的部分
例如 字符串 a 没有前后缀
字符串 ab 没有前后缀
字符串 aba 没有前后缀
字符串 abab 前后缀 ab
字符串 ababa 前后缀 可以是 a 可以是 aba 我们取长度最长的 即 aba
第一位时 next值固定为0
其他情况 取其公共最长前后缀的长度+1 没有则为1
因为一共子串有8位 所以在子循环内一共需要获取 8次前后缀
这里我们定义一个next数组 长度为8 里面的元素分别对应子串各个子循环内的 前后缀长度
第1位不匹配时 获取字符串为a 没有前字符串 没有前后缀 那么next[1] = 0
第2位不匹配时 获取字符串为ab 有前字符串a 没有前后缀 那么next[2] = 1
第3位不匹配时 获取字符串为aba 有前字符串ab 没有前后缀 那么next[3] = 1
第4位不匹配时 获取字符串为abab 有前字符串aba 前后缀 a 那么next[4] = 2
第5位不匹配时 获取字符串为ababa 有前字符串abab 前后缀 ab 那么next[5] = 3
第6位不匹配时 获取字符串为ababaa 有前字符串ababa 前后缀 aba 那么next[6] = 4
第7位不匹配时 获取字符串为ababaab 有前字符串ababaa 前后缀 a 那么next[7] = 2
第8位不匹配时 获取字符串为ababaabc 有前字符串ababaab 前后缀 ab 那么next[8] = 3
next数组为[ 0, 1 , 1 ,2 , 3, 4 ,2, 3 ]
后来有人发现 KMP还是有缺陷的 比如 当子串 T = "aaaaax"
在5位发生不匹配 此时 next[5] = 4 接着就是 子串中的第四位a与 主串当前位置字符比较
因为子串第五位等于子串第四位相同 所以可以得出该步骤也不匹配 此时 next[4] = 3
依然不匹配 直到next[1] = 0
我们可以发现由于T串中的 2 3 4 5 位置都与首位a 相等 中间的过程都是多余的
那么可以用首位的next[1] 的值 去替代与它相等的字符后续的next[x]的值
⑺ kmp算法什么意思
1.KMP算法是一种改进的字符串匹配算法，由克努特，莫里斯和普拉特同时发现，因此人们称它为克努特·莫里斯·普拉特操作，简称KMP算法；
2.KMP算法喊掘的关键是利用匹配失高历败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现戚渗搜就是实现一个next函数，函数本身包含了模式串的局部匹配信息；
3.在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。
⑻ 没有使用贪心策略的算法
KMP算法。
KMP算法是一种改进的字符串匹配算法。为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀，在中逗缓匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配指睁；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。
贪心算法，又称贪婪算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的卖模是在某种意义上的局部最优解。
⑼ 图解KMP字符串匹配算法
kmp算法跟之前讲的bm算法思想有一定的相似性。之前提到过，bm算法中有个好后缀的概念，而在kmp中有个好前缀的概念，什么是好前缀，我们先来看下面这个例子。
观察上面这个例子，已经匹配的abcde称为好前缀，a与之后的bcde都不匹配，所以没有必要再比一次，直接滑动到e之后即可。
那如果前缀中有互相匹配的字符呢？
观察上面这个例子，这个时候如果我们直接滑到好前缀之后，则会过度滑动，错失匹配子串。那我们如何根据好前缀来进行合理滑动？
其实就是看当前的好前缀的前缀和后缀是否有匹配的，找到最长匹配长度，直接滑动。鉴于不止一次找最长匹配长度，我们完全可以先初始化一个数组，保存在当前好前缀情况下，最长匹配长度是多少，这时候我们的next数组就出来了。
我们定义一个next数组，表示在当前好前缀下，好前缀的前缀和后缀的最长匹配子串长度，这个最长匹配长度表示这个子串之前已经匹配过匹配了，不需要再次进行匹配，直接从子串的下一个字符开始匹配。
我们是否每次算next[i]时都需要每一个字符进行匹配，是否可以根据next[i - 1]进行推导以便减少不必要的比较。
带着这个思路我们来看看下面的步骤：
假设next[i - 1] = k - 1;
如果modelStr[k] = modelStr[i] 则next[i]=k
如果modelStr[k] != modelStr[i]，我们是否可以直接认定next[i] = next[i - 1]？
通过上面这个例子，我们可以很清晰地看到，next[i]!=next[i-1]，那当modelStr[k]!=modelStr[i]时候，我们已知next[0],next[1]…next[i-1]，如何推导出next[i]呢？
假设modelStr[x…i]是前缀后缀能匹配的最长后缀子串，那么最长匹配前缀子串为modelStr[0…i-x]
我们在求这个最长匹配串的时候，他的前面的次长匹配串（不包含当前i的），也就是modelStr[x…i-1]在之前应该是已经求解出来了的，因此我们只需要找到这个某一个已经求解的匹配串，假设前缀子串为modelStr[0…i-x-1],后缀子串为modelStr[x…i-1],且modelStr[i-x] == modelStr[i],这个前缀后缀子串即为次前缀子串，加上当前字符即为最长匹配前缀后缀子串。
代码实现
首先在kmp算法中最主要的next数组，这个数组标志着截止到当前下标的最长前缀后缀匹配子串字符个数，kmp算法里面，如果某个前缀是好前缀，即与模式串前缀匹配，我们就可以利用一定的技巧不止向前滑动一个字符，具体看前面的讲解。我们提前不知道哪些是好前缀，并且匹配过程不止一次，因此我们在最开始调用一个初始化方法，初始化next数组。
1.如果上一个字符的最长前缀子串的下一个字符==当前字符，上一个字符的最长前缀子串直接加上当前字符即可
2.如果不等于，需要找到之前存在的最长前缀子串的下一个字符等于当前子串的，然后设置当前字符子串的最长前缀后缀子串
然后开始利用next数组进行匹配，从第一个字符开始匹配进行匹配，找到第一个不匹配的字符，这时候之前的都是匹配的，接下来先判断是否已经是完全匹配，是直接返回，不是，判断是否第一个就不匹配，是直接往后面匹配。如果有好前缀，这时候就利用到了next数组，通过next数组知道当前可以从哪个开始匹配，之前的都不用进行匹配。
⑽ kmp算法什么意思
KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。
在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。
对于next[]数组的定义如下：
1) next[j] = -1 j = 0
2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如：
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0时，表示P[0...k-1]=P[j-k,j-1]
因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。