字符串模式匹配算法--详解KMP算法
在软考的复习中，看到过几次 字符串的模式匹配算法。看起来挺难的。所以花了点时间查了查关于字符串匹配的算法。下面详细介绍一下KMP模式匹配算法
什么是字符串的匹配？
在文章中进行查找。需要找到要查找的内容所在的位置。就是字符串的匹配。
朴素的模式匹配算法
朴素的模式匹配算法，就是把要查找的内容，一步步的与要查找的文章进行进行比较。如果匹配失败，则主串和字串回溯。字串位置加1.重新匹配。
模式匹配算法的流程如下：
在匹配失败的情况下，模式串仅右移一个 之后。在从头开始匹配。
两个for循环
For i=1 to length(主串)-length(模式串)+1
For j=1 to length(模式串)
所以时间复杂度为：O((n-m+1)*m) 在模式串较小的情况下，时间复杂度为O(mn)
KMP匹配算法：
在看这个例子的时候，如果匹配失败。令模式串右移一个位置。重新开始匹配。这种情况。主串与模式串的指针都要回溯。
在朴素的匹配算法中，无论已经匹配正确了多少个字符，在遇到不配的情况下，指针就要进行回溯。重新开始下一轮匹配。这样就会造成资源的浪费。
KMP算法，就是消除这种浪费。KMP算法要利用已经匹配好的部分字符串。
用一个例子来说明，是如何利用已经匹配的字符串的。
c匹配失败。但是前面已经有匹配成功的子串为“abaaba“ 所以 要利用这个已经匹配好的字符串。
只有在这种情况下，右移才能最大化。才能使得指针不用回溯。
在已经匹配成功的子串中。是如何求出最大偏移量呢？
可以利用的子串：
在这就要使用，字符串的前缀 和后缀了。
比如字符串“ABCD”的
前缀：A、AB、ABC、ABCD
后缀：D、CD、BCD、ABCD
只要找到，前缀和后缀中 相同的部分。就是可以利用的部分。
例子中：
abaaba前缀：a、ab、aba、abaa、abaab
abaaba后缀：a、ba、aba、aaba、baaba
找到前缀和后缀中的公共部分长度最大的为"aba" 所以要利用的串为"aba"。
模式串的右移量：
利用已经匹配好的字符串，来确定子串 右移的位数。利用next函数。
根据以上的描述，指针一直向右，不回溯。所以要匹配的长度为m+n
所以KMP算法的时间复杂度为：O(m+n)
在KMP匹配算法中，常常看到。一个next函数：
形式如：
在模式串 abaabaca中。对应的next串为：01122341
Next[j]表示，在j匹配出错之后。要利用前面的子串，所能使用的子串长度+1。
至于next[j]表示的是什么。查了好多也不知道干什么用的。如果读者对next函数有了解，请留言。
参考博客：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
