KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。

以下借用http://www.cnblogs.com/c-cloud/p/3224788.html的部分内容  这种算法不太容易理解，网上有很多解释，但读起来都很费劲。直到读到这篇文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。

首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。  当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

因为空格与Ｃ不匹配，搜索词还要继续往后移。

逐位比较，直到发现C与D不匹配。于是，继续将搜索词向后移动。

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。

——就是回溯到存在”对称“的地方。

从第2部分图中可以分析得出，当扫描到模式串中某一位发现不匹配，总是回溯到在这一位之前的部分模式串存在重复的地方。

所以，next(j)就是当模式串第j位不匹配时即将要退回到的字母标号。

不管第一位和第二位是什么，第一位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;

观察第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;

详解完毕，希望大家喜欢。

原文 https://blog.csdn.net/nanami809/article/details/49367159

文章来源: hiszm.blog.csdn.net，作者：孙中明，版权归原作者所有，如需转载，请联系作者。

原文链接：hiszm.blog.csdn.net/article/details/79669493