首页 > 代码库 > kmp算法简明教程
kmp算法简明教程
在字符串s中寻找模式串p的位置，这是一个字符串匹配问题。
举例说明：
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4
在kmp算法发明之前。人们使用这种算法：
‘‘‘原始的求子串位置算法，O( m * n )‘‘‘def string_index_of( pstr, pattern, pos = 0 ): str_index = pos pattern_index = 0 pattern_len = len( pattern ) while str_index < len( pstr ) and pattern_index < pattern_len: if pstr[ str_index ] == pattern[ pattern_index ]: str_index += 1 pattern_index += 1 else: str_index = str_index - pattern_index + 1 pattern_index = 0 if pattern_index == pattern_len: return str_index - pattern_index return -1pstr = ‘i am caochao, i love coding!‘pattern = ‘ao‘print( string_index_of( pstr, pattern, 7 ) )print( pstr.find( pattern ) )
当s[4]与p[4]失配时，主串s回溯到i=1，模式串回溯到j=0，然后从此位置继续匹配。显然这种做法效率低下，假设s长度为n，p长度为m，则其时间复杂度为O(m*n)。
现考虑这样一个问题，当s与p匹配到位置i，j处，s[j]不等于p[j]，如果此时保持i不变，p串中从k(0<k<j)处继续匹配，这样无需回溯i的做法这就是我们要讲到的kmp算法。那么应当如何取得这个k值？可以预先求出p中每个失配的j处需要跳转到的位置k(next[j])，这就是kmp算法中的next数组。
kmp算法步骤如下：
1，初始化i，j均为0，
2，依次往后比较s[i]与p[j]，若相等则i，j各自加1，否则保持i不变，j=k(next[j])。若某时刻求得j值为-1，i，j也各自加1然后继续匹配
3，重复步骤2
依据上述分析可知，kmp算法中最关键之处在于k值的取法。在匹配进行到s[i]不等于p[j]时，假设应当让s[i]与p[k]继续比较(0<k<j)，那么p中前k个字符必须满足，且不能存在k‘>k满足等式1：
等式1，p[0,k-1]=s[i-k,i-1]
而在i，j之前已经匹配的字符里存在等式2：
等式2，p[j-k,j-1]=s[i-k,i-1]
由此，可以推出等式3：
等式3，p[0,k-1]=p[j-k,j-1]
至此，k值的取法已经非常明显，即在p串中取最大的k(0<k<j)，使得p中开始的k个字符与p[j]之前的k个字符相等。这样就可在s[i]不等于p[j]时，尽可能在距离p[0]远的位置处继续匹配，从而提高匹配效率。
从上面的分析中可以给出k，即next[j]的定义：
1，j=0时，next[j]=-1
2，next[j] = max{k|0<k<j且p[0,k-1]=p[j-k,j-1]}
3，其它情况，next[j]=1
递推求next数组：
从next[j]的定义出发，可以采用递推的方式求得next[j]:
首先，next[0]=-1
令next[j]=k(0<k<j)，则表明在p中存在k，且不存在k‘>k满足下列关系：
p[0,k-1]=p[j-k,j-1]
那么next[j+1]的取值有3种情况，
1，若p[k]=p[j]，则表明在p中存k，且不存在k‘>k满足关系p[0,k]=p[j-k,j]，那么next[j+1]=k+1，即
next[j+1]=next[j]+1
2，若p[k]不等于p[j]，此时可把求next函数的过程看成模式匹配的过程，即p既是主串又是模式串。而在模式匹配过种中，此时应当让p[j]与p[next[k]]继续比较。
为了便于理解，这里令next[k]=k‘。
若p[j]=p[k‘]时，next[j+1]=k‘+1，即next[j+1]=next[k]+1，也即
next[j+1]=next[next[j]]+1
同理若p[j]不等于p[k‘]，那么继续让p[j]与next[k‘]比较，依次类推，直至k‘=-1时：
next[j+1]=0
代码实现如下：
‘‘‘kmp求next[j]数组‘‘‘def kmp_get_next( pattern ): i = 0 j = -1 _next = [ 0 ] * len( pattern ) _next[ 0 ] = -1 while i < len( pattern ) - 1: if j == -1 or pattern[ i ] == pattern[ j ]: i += 1 j += 1 _next[ i ] = j else: j = _next[ j ] return _next
优化的求next数组方法：
考虑如下模式串:
j = 0 1 2 3 4p = a a a a bnext[j] = -1 0 1 2 3
若某时刻s[i]与p[3]不相等，依据next[3]指示应当让s[i]与p[2]继续比较，因p[3]与p[2]相等，这一步明显是多余的。推广到普遍情况，在求next数组过程中，如果next[i]=j且p[i]=p[j]，那么令next[i]=next[j]。代码如下：
‘‘‘kmp求next[j]数组‘‘‘def kmp_get_next( pattern ): i = 0 j = -1 _next = [ 0 ] * len( pattern ) _next[ 0 ] = -1 while i < len( pattern ) - 1: if j == -1 or pattern[ i ] == pattern[ j ]: i += 1 j += 1 if pattern[ i ] == pattern[ j ]: _next[ i ] = _next[ j ] else: _next[ i ] = j else: j = _next[ j ] return _next
预先求得next[j]数组后，kmp算法代码实现如下：
‘‘‘kmp求子串位置‘‘‘def kmp_index_of( pstr, pattern, pos = 0 ): _next = kmp_get_next( pattern ) str_index = pos pattern_index = 0 pattern_len = len( pattern ) while str_index < len( pstr ) and pattern_index < pattern_len: if pattern_index == -1 or pstr[ str_index ] == pattern[ pattern_index ]: str_index += 1 pattern_index += 1 else: pattern_index = _next[ pattern_index ] if pattern_index == pattern_len: return str_index - pattern_index return -1pstr = ‘i am caochao, i love coding!‘pattern = ‘ao‘print( kmp_index_of( pstr, pattern, 7 ) )print( pstr.find( pattern ) )
最后，对比下普通算法与kmp算法解决本文开始提出的问题匹配过程：
普通算法：
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4s[4]不等于p[4]，令i=1，j=0
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4
s[1]不等于p[0]，令i=2，j=0
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4
s[3]不等于p[1]，令i=3，j=0
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4
限于篇幅，略过中间n步，跳至i=9，j=0
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4
一路i++，j++，直到i=14，跳出循环结束匹配，并返回9。
kmp算法：
p串next数组为：
j = 0 1 2 3 4p = a b a a bnext[j] = -1 0 0 1 1next数组优化过后变为：
j = 0 1 2 3 4p = a b a a bnext[j] = -1 0 -1 1 0
下面开始匹配：
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4
s[4]不等于p[4]，令j=0
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4
s[4]不等于p[0]，next[0]=-1，因此i，j各自加1。i=5，j=0
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4
i++，j++，直到s[9]不等于p[4]，令j=0
i = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 s = a b a a c a b a a a b a a b p = a b a a b j = 0 1 2 3 4
一路i++，j++，直到i=14，跳出循环结束匹配，并返回9。
通过对比可以看出，kmp算法比普通算法快得多，只要预先求出模式串next数组，则整个匹配过程中i无需回溯，时间复杂度亦由普通算法O(m*n)提升为O(m+n)。
kmp算法简明教程