Yangming's Blog

beware the barrenness of a busy life

KMP回顾

04 Feb 2019 » algo

背景

在计算机系统中,字符串操作是相当常见的。而字符串操作中,我们最常见的操作就是字符串匹配,即,我们有一个很长的文本S和一个模式串P,需要找到S中是否存在P的匹配,有的话就返回匹配的位置。显而易见的做法如下:

for i in range(len(S)):
  j=0
  ii = i
  while j<len(P) and ii < len(S) ans S[ii] == P[j]:
    j+=1
    ii+=1
  if j==N:
    return i-len(P)
return -1 # 没找到	

该方法对于S的每个位置都会向后遍历len(P)的距离,判断该位置是否是匹配的;因此,算法复杂度为O(len(S)*len(P))。进一步思考,即使P[k]没有匹配,但是(P[j]==S[i] j<k),那么我们可以利用这一条件减少算法的重复比较,即:

kmpSearch

假设对于P来说,有P[j-k],…,P[j] == P[0],…,P[k];那么当P[j+1] != S[i]时,i不动,j=k(不必退回0)。i假设我们已知了满足如上条件的的每个位置的k,即,有数组nxt;则上述算法变成:

#! /usr/local/bin/python3.7


def kmpSearch(S, P):
    nxt = getNxt(P)
    j=0
    i=0
    while i<len(S):
        if j<len(P) and i<len(S) and P[j] == S[i]:
            i+=1
            j+=1
        elif j<len(P) and i<len(S) and P[j] != S[i]:
            if j==0:
                i+=1
            else:
                j = nxt[j-1]+1

        if j == len(P):
            return i-len(P)
    return -1

print(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"))

最后问题就是如何找到getNxt。

Next数组

基于P[j-k],…,P[j] == P[0],…,P[k]成立,那么nxt[j-k],…,nxt[j] = 0,…,k。初始化两个一前一后的指针,如果前后两个元素不相等,那么前者迭代;直到找到P中前后相同的元素作为起点,那么对于前后相等的船有nxt[j] = i;否则,i=nxt[i-1]+1。即,最后有:

#! /usr/local/bin/python3.7


def kmpSearch(S, P):

    def getNxt(P):
        nxt=[-1 for i in range(len(P))]
        j=1
        i=0
        while j<len(P):
            if P[j] == P[i]:
                nxt[j] = i
                j+=1
                i+=1
            elif i==0:
                j+=1
            else:
                i=nxt[i-1]+1
        return nxt



    nxt = getNxt(P)
    j=0
    i=0
    while i<len(S):
        if j<len(P) and i<len(S) and P[j] == S[i]:
            i+=1
            j+=1
        elif j<len(P) and i<len(S) and P[j] != S[i]:
            if j==0:
                i+=1
            else:
                j = nxt[j-1]+1

        if j == len(P):
            return i-len(P)
    return -1

print(kmpSearch("ABABDABACDABABCABAB", "ABABCABAB"))