串的模式匹配算法主要有两种，一是简单模式匹配，而是KMP算法。
简单模式匹配算法很容易理解，每一次从主串的第一个位置起和模式串的第一个字符开始比较，如果相等就按照顺序一直比下去，如果不相等就把模式串和第二个位置开始继续进行比较，最后若匹配成功则返回主串中与模式串匹配的第一个字符的位置，虽然简单易懂也容易实现，但过程及其繁琐，有许多冗余的步骤降低了匹配效率。
因此采用无回溯效率更高KMP算法，它哪哪都好除了看不懂，书本上的话简直没法看，感觉在讲天书！！！各种下标各种公式根本看不懂。
以下是我对KMP算法的个人理解：
KMP和简单模式匹配算法的区别就是，主串和模式串匹配不成功时，简单模式匹配得屁颠屁颠跑回去，从上一次比较的下一个字符开始继续比较，就算中间有大部分比较过得，就算明知道第一个字符就不匹配的但我还是得去比，没办法，所以效率低下且各种回溯。
而KMP算法是当在某个位置匹配不成功的时候可以根据之前匹配结果，从模式串的另一个位置开始匹配字符串，而不必从头开始，只需要将模式串后移即可，大大的提升了匹配效率，但如何确定后移的位置点呢？
T1 T2 ......Ts Ts+1 Ts+2 .... Ts+j-k-1 Ts+j-k .... Ts+j-1 Ts+j ....
P0 P1 P2 ..... Pj-k-1 Pj-k ..... Pj-1 Pj ......
P0 P1 .... Pk ........
如上，只要求得k值就能知道模式串后移的目标位置。为方便说明，取数组从1开始计数。在这里定义next[j]数组，1<j<m,m是模式串的长度，含义为当模式串第j个位置匹配失败后，应该从next[j]处的字符继续与主串比较。
接下来才是重点：
众所周知，KMP算法的灵魂就是求next数组和nextval数组，不管各种资料怎么说，以我自己的思路先走一遍求解next数组的步骤：
以例题来说明：
模式串：ababaaababaa
口诀①：当j=1的时候，next[j]=0。
口诀②：子串的前后缀没有匹配部分，并且子串不为空，next[j]=1，用人话来说就是模式串里面没有任何一个字符能够匹配成功，没有任何重复元素，就跟abcd这种一样，遇见这种给它赋1就完事了。
口诀③：子串前后有匹配部分，就去数一数匹配部分有多长，比如aba，俩a匹配了，在一起互gay，长度为1，那么就给next赋匹配子串长度+1！！！即next[j]=2
例题计算步骤：
1.j=1,next[1]=0
2.j=2,模式串为a，没有匹配元素，next[2]=1
3.j=3,模式串为ab，没有匹配元素，next[3]=1
4.j=4,模式串为aba，前后串有匹配的a，next[4]=1+1=2
5.j=5,模式串为abab，ab匹配，next[5]=2+1=3
.......
最后求解的答案为：
0 1 1 2 3 4 2 2 3 4 5 6
再然而，这种KMP方法还是有缺陷，一些情况下也会产生冗余比较，原因不加以说明，直接记录步骤。
还是模式串ababaaababaa.
用P1~Pm来表示模式串的第i个位置处的字符（1<i<m）
另取k(-1<k<m-1)，k=next[j]
比较Pi与Pk
若相等，则继续判断k值是否为0，若k=0，则nextval[j]=k,若k！=0，则nextval=nextval[next[j]].
若不等，nextval[j]=k=next[j]
解题步骤：
1.
j=1
nextval[1]=0
2.
j=2
P2=b
Pk(k=next[2]=1)=P1=a
Pi!=Pk,nextval[j]=k=1
3.
j=3
P3=a
Pk(k=next[3]=1)=P1=a
Pi=Pk,nextval[j]=nextval[next[3]]=0
.....
最后结果为：
0 1 0 1 1 2 0 1 0 1 0 2
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
