东莞网站优化方案,wordpress 换服务器,个人主页签名引导进入橱窗,网站seo注意事项在http://blog.csdn.net/u012613903/article/details/79004094中写到了如何手工去求一个NEXT数组#xff0c;这个在很多考试中可以用来解题。但是在实际的使用中#xff0c;NEXT数组究竟发挥着什么样的作用#xff0c;如何用代码实现KMP算法呢#xff1f;
KMP算法是用来确…在http://blog.csdn.net/u012613903/article/details/79004094中写到了如何手工去求一个NEXT数组这个在很多考试中可以用来解题。但是在实际的使用中NEXT数组究竟发挥着什么样的作用如何用代码实现KMP算法呢
KMP算法是用来确定一个串是否能在另一个串中找到与之完全匹配的子串那么首先来看一个字符串匹配的实际例子
被匹配的字符串 abcdabef 要匹配的字符串 abcdabw 下面开始进行匹配i代表被匹配的字符串的当前字符下标j代表要匹配的字符串的当前字符下标。 012345i abcdabefabcdabw 012345j 可以看到在{e,w}的位置匹配失败了如果使用暴力的方法做那么下一次的匹配就变成了这个样子 0i234567abcdabef abcdabw j123456 这时候 i i-j1j0这就是暴力算法的思想一旦匹配失败就让要匹配的字符串从头开始与被匹配的字符串进行匹配。 我们来观察第一次匹配失败后的情况 012345i abcdabefabcdabw 012345j 在要匹配的字符串的w位置往前看看到♦的ab与实心♦的ab就是我们要求的最长的相同前缀与后缀字符串
其实它们代表的实际意义是这样的
在ew位置无法进行匹配了但是在w之前的要匹配的字符串的所有字符都与在e之前的被匹配的字符串的所有字符完全匹配了这是个前提标记为1
下面具体分析实际情况 abcdabefabcdabw 在ew位置匹配失败了我们不想使用暴力方法想省力那该怎么办呢
要匹配的串中的w和被匹配串的e不匹配进行下次匹配的时候必然会有要匹配串中的w之前的某个字符取代w。也就是要将要匹配的串向右平移一个量(j这个量i)。这里我们列出所有的平移情况
(1) abcdabef abcdabw (2) abcdabef abcdabw (3) abcdabef abcdabw (4) abcdabef abcdabw ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
(5) abcdabef abcdabw (6) abcdabef abcdabw 上面就是所有的平移情况情况123从第一个就不匹配情况4从第三个不匹配56不需要讨论可以看到在4之前都是从第一个字符起两个串就不匹配直到4才出现不是在第一个字符就不匹配的情况。然后再看4中的匹配上的字符串居然是 ab是要匹配的 最长的相同前缀与后缀字符串。为什么会这样这就用到了上面的前提1 。
再回到最初不匹配的情形下 abcdabefabcdabw 正如前提1所说ew之前两个字符串完全匹配也就是完全相同。所以要求被匹配串e之前与要匹配串从0开始相同的最长子串串也就变成了在要匹配字串中求w之前与要匹配串中从0开始相同的最长子串abcdabefabcdabw
就像图中表示的那样要求黄色与红色的关系就是求绿色与红色的关系所以我们在求NEXT数组时所求出的最长的相同前缀与后缀字符串就是在不匹配的位置之前被匹配字符串中与要匹配的字符串中从0开始所以字符完全相同的最长的子串。然后(1)-(2)-(3)-(4)的平移过程其实就是使用暴力法的过程KMP算法就是利用了这个特性在某个位置发生不匹配的情况后直接将比较情况变成4跳过了1、2、3这些从一开始就不匹配的匹配情况而且断定了在ab已经匹配只需要测试ab之后的字符是否匹配就可以了如下图所示 012345i7 abcdabef abcdabw 01j3 在i的位置发生了不匹配直接平移到了上图中的情况然后直接从j2位置的要匹配字符串的字符与i6位置的被匹配字符串的字符进行对比就可以了为什么能跳过暴力算法的从开始就不匹配的步骤并且确定了这次比较中已经匹配的字符串的长度呢
个人理解在i位置发生了不匹配的情况我们从i往前逐渐加大长度来取得字符串然后确定这个字符串在要匹配的串中从0开始能否得到知道走到得不到的时候
也就是恰好如上图中的 a,b,c中的c与 d,a,b中的b不想同的时候由于d的出现就可以确定它们从一开始就无法匹配而反之取到 ab的时候说明ab是可以匹配的只需要确定i以及i之后与ab之后是否能够匹配就可以了。 最后确定一下j与NEXT数组的关系求出要匹配的字符串的NEXT数组的值如下 abcdabw0111123 在这里jNEXT值-1 其中当NEXT为0的时候j-1这种情况说明第一个字符就不匹配在算法中i会直接1然后j也直接1也就是从被匹配串的第i1位置和要匹配串从0开始进行匹配。下面是算法的具体实现最近在学python所以就用python写了PS求next数组不是最优化的算法 # -*- coding:utf-8 -*-
# Author: Evan Midef kmp(haystack, needle):slen len(haystack)plen len(needle)nexts [0] * plenget_next(needle, nexts)print(nexts)i 0j 0当haystack[i] needle[j]的时候直接ij看下一个是否匹配
一旦不匹配那么i不变jnexts[j]-1边界情况下jnexts[0]-1-1;
这中情况说明没有满足的NEXT值也就是在i前面的已匹配字符串的长度为-1
也就是在i1前面已匹配的字符串的长度为0即从i1与j0处开始比较
恰好也对应i i1j( 0)然后看下一个是否匹配
while i slen and j plen:if haystack[i] needle[j] or j -1:i 1j 1else:j nexts[j]-1if j plen:return i-jelse:return -1
设要求的字符串为A
在求next数组的时候我们已经求的了位置j的NEXT值为k1
也就是说在要求的字符串中从[0到k-1]与[j-k到j-1]完全相同
所以如果A[k]A[j]的时候只需要jknexts[j]k1 就求的了j1位置的NEXT值
当A[k]!A[j]的时候我们把A进行复制赋值一个A让k对应与A,让j对应于A且容易得到A的NEXT数组和A完全相同
就可以看作在A中[0,k-1]与A中[j-k,j-1]完全相同也就是匹配成功但是在{j,k}处匹配失败所以j不变而是将
k赋值为next[k]-1在k之前的所有NEXT值是已经求得的最差的情况k会取到NEXT[0]-1也就是k-1这时在j1之前的A
的长度是k10所以A[j1]要与A[0]对应也就是k0所以也需要执行操作j ( j1),k( 0) 然后nexts[j]k1
def get_next(needle, nexts):al len(needle) #求出要求NEXT数组的字符串的长度nexts[0] 0 #NEXT[0]是恒定值0k -1j 0while j al - 1: if k -1 or needle[j] needle[k]:j 1k 1nexts[j] k1else:k nexts[k]-1print(kmp(hello, ll))
