KMP算法求next数组

算法 KMP

---

KMP算法是一种快速模式匹配算法，其中最关键的部分是根据模式串生成next数组。

next数组的含义

设模式串为$p_0p_1p_2 \ldots p_{i-1}$，next数组为$n_0n_1n_2 \ldots n_{i-1}$.

$$n_j=\begin{cases} -1,& j=0\\ 0,&0 \lt j \lt i,&0 \lt k \lt j,&\lnot\exists k,& p_0p_1p_2 \ldots p_{k-1}=p_{j-k}p_{j-k+1} \ldots p_{j-1}\\ max(k),&0 \lt j \lt i,&0 \lt k \lt j,&\exists k,&p_0p_1p_2 \ldots p_{k-1}=p_{j-k}p_{j-k+1} \ldots p_{j-1} \end{cases}$$

1.暴力求解

这种方法的主要思路是根据next数组的定义将k从j-1到0暴力尝试，判断是否存在对应的序列。

def ViolateGetNext(p):
    plen = len(p)
    n = [-1]*plen
    for j in range(1,plen):
        k = j - 1
        while k > 0:
            #如果存在长度为k的相同前缀和后缀
            if p[:k] == p[j-k:j]:
                break
            k -= 1
        #如果不存在这样的k，k此时为0
        n[j] = k
    return n

设模式串为
$ABCDABD,n[5]$的求解过程如下:
$k=4$
$ABCD \neq BCDA, k=3$
$ABC \neq CDA, k=2$
$AB \neq DA, k=1$
$A = A, n[5]=k$

2.递归求解

暴力求解每次在计算$n[j]$时都是独立的，而实际上求解$n[j+1]$是可以利用到$n[0,\ldots,j]$的，递归算法就是基于这样的思路。
设模式串为$p_0p_1p_2 \ldots p_{i-1}$,已经计算出$n_0n_1n_2 \ldots n_j$,如何计算$n_{j+1}$?
1.$k=n_j,k$为当前尝试的前缀后缀相等的最大值,即$p_0p_1p_2 \ldots p_{k-1}=p_{j-k}p_{j-k+1} \ldots p_{j-1}$
2.如果$k==-1$,则$n_{j+1}=0$,算法结束
3.如果$p_k==p_j$，则$n_{j+1}=k+1$,算法结束
4.$\exists k' \lt k, p_0p_1p_2 \ldots p_{k'-1}=p_{j-k'}p_{j-k'+1} \ldots p_{j-1}=p_{k-k'}p_{k-k'+1} \ldots p_{k-1}$,由定义可知$k'=n_k$
5.将$k'$赋值给$k$，转到步骤2

def ReGetNext(p,j):
    if j == 1:#j指示字符串的长度
        return [-1]
    #计算p前1到j-1个字符的next数组
    n = ReGetNext(p,j-1)
    k = n[j-2]
    while k != -1:
        if p[j-2] == p[k]:
            break
        k = n[k]
    #k+1为第j个字符next值
    n.append(k+1)
    return n

设模式串为
$ABCDABD,n[5]$的求解过程如下:
$n=[-1,0,0,0,0]=ReGetNext(p,5)$
$k=0=n[4]$
$P[4] = P[0](A=A),n=[-1,0,0,0,0,k+1]$

3.递归展开求解

这种方法和递归的思路类似，但是不如递归清晰。

def GetNext(p):
    plen = len(p)
    n = [-1]*plen
    k = -1
    j = 0
    while j < plen -1:
        if k == -1 or p[j] == p[k]:
            j += 1
            k += 1
            n[j] = k
        else:
            k = n[k]
    return n

三种算法比较

计算next数组的关键还是在于彻底理解其含义。通过next数组的数学定义可以很容易的得到一个暴力解法，这个方法思路最清晰，第二种递归则是利用了next数组前后的关系得到了一个效率更高的算法，第三种和第二种类似，减少了递归调用。以模式串$ABCDABD$分析三种算法的效率，三种算法的字符比较次数分别为15,5,5