大家好，欢迎来到IT知识分享网。
版权声明：本文原创内容权归 http://blog.csdn.net/nanami809 所有，欢迎转载，但必须在明显位置保留此段声明，否则保留追究法律责任的权利.
一、定义
KMP算法时间复杂度为O(m+n)，空间复杂度为O(m)
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。
二、图解原理
以下借用http://www.cnblogs.com/c-cloud/p/3224788.html的部分内容
这种算法不太容易理解，网上有很多解释，但读起来都很费劲。直到读到这篇文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。
1.
首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
2.
因为B与A不匹配，搜索词再往后移。
3.
就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。
4.
接着比较字符串和搜索词的下一个字符，还是相同。
5.
直到字符串有一个字符，与搜索词对应的字符不相同为止。
当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。
6.
因为空格与Ｃ不匹配，搜索词还要继续往后移。
7.
逐位比较，直到发现C与D不匹配。于是，继续将搜索词向后移动。
8.
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。
三、详解
nextval是更新优化了next数组，以下讲解第二种
| 标号（j） | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 模式串（P） | A | B | C | D | A | B | D |
1、KMP算法的核心思想
——就是回溯到存在”对称“的地方。
- 注意，这里的“对称”不是指ABCCBA，而是指例如”ABCABC”中队前队尾都分别有1个”ABC”,又例如”ABCCCCCAB”中队前队尾都分别有一个”AB”。
2、看图说话
从第2部分图中可以分析得出，当扫描到模式串中某一位发现不匹配，总是回溯到在这一位之前的部分模式串存在重复的地方。
- 例如2.5中找不到字母D（标号4），D之前串为”ABCDAB”,存在队前队尾重复”AB”（2个字符），因此退回到队首的“AB”后一位C（标号3）。
- 例如2.6中找不到字母C（标号3），C之前串为”AB”，不存在重复的（0个字符），因此退回到队首最前面（标号1）。
所以，next(j)就是当模式串第j位不匹配时即将要退回到的字母标号。
- 以上例子也可以看出，如果有2个字符重复，就退到第3位，如果有0个字符重复，就退到第1位。显然这是一个+1的关系。
3、next计算过程
不管第一位和第二位是什么，第一位next(1)=0，第二位next(2)=1，这是固定的。
当j=3时，P(j)=C,C之前有”AB”，不存在重复(0位），所以next(3)=0+1=1;
当j=4时，P(j)=D,C之前有”ABC”，不存在重复(0位），所以next(4)=0+1=1;
当j=5时，P(j)=A,C之前有”ABCD”，不存在重复(0位），所以next(5)=0+1=1;
当j=6时，P(j)=B,C之前有”ABCDA”，存在重复”A”(1位），所以next(6)=1+1=2;
当j=7时，P(j)=D,C之前有”ABCDAB”，存在重复”AB”(2位），所以next(7)=2+1=3;
4、nextval=对next的优化
观察第5位”A”,当它不匹配时，按照next行回溯到标号1也为字母A，这时再匹配A是徒劳的，因为已知A不匹配，所以就继续退回到标号1字母A的next(1)=0。为了直接点进行优化，就有了nextval行:
- 只看前面有重复字母的几位就可以。
j=5，P(5)=A，next(5)=1，P(1)=A=P(5)，所以nextval(5)=next(1)=0;
j=6，P(6)=B，next(6)=2，P(2)=B=P(6)，所以nextval(6)=next(2)=1;
j=7，P(7)=D，next(7)=3，P(3)=C!=P(7)，所以nextval(7)=next(7)=3;
结果：
| 标号（j） | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 模式串（P） | A | B | C | D | A | B | D |
| next | 0 | 1 | 1 | 1 | 1 | 2 | 3 |
| nextval | 0 | 1 | 1 | 1 | 0 | 1 | 3 |
例题eg：字符串′ababaabab′的nextval为()
0 1 2 3 4 5 6 7 8
s[0]与s[5]重复(因为多了一个a，无法找到长度为3的重复字符串，这只能是s[0]和s[5]重复)，长度为1，故next[6] = 1。
(严谨来看这么表述是有问题的，因为nextval[2]表示nextval数组中
第3个数值，而nextval[s[0]]表示的是s[0]对应的字母‘a’所对应的nextval值 -1，这里nextval[]的用法并不严谨，只是为了表述方便
)。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/25743.html
