字符串匹配之KMP算法中的pnext表

pnext表的分析

上篇我们提到了最后是构建一个pnext表，记录着每个字符匹配需要移动的长度的位置信息，接着上篇的内容，我们来分析下pnext表的构造。

还是举个栗子:

ababcabcacbab
  abcac  # 状态1
     abcac  # 状态2

如状态1所示，这时位置i的字符是最后一个c，对应的位置k_i的字符应该是b。由此可知：

• 模式串移动之后，作为下一个用于匹配的字符串的新位置，其前缀子串应该与匹配失败的字符串之前同样长度的子串相同。
• 如果匹配在模式串的位置i失败时，而位置i的前缀子串中满足杉树条件的位置不止一处，那么只能做最短的移动，将模式串移动到最近的满足上述条件的位置，保证不遗漏可能的匹配。

现在考虑pnext表的构造问题，首先已知k_i的值只依赖模式串本身的前i的字符。在下面的分析和讨论中参考下图。

图一

 首先，如图1状态(1)所示，目标串中位置j之前的i个字符，也就是模式串的前i个字符，也就是说，目标串中的子串t_j-i…t_i-1就是p₀…p_i-1。

现在需要找一个位置k，下次匹配用pk与前面匹配失败的tj比较，也就是把模式串移动到pk与tj对准的位置，也即状态(2)，如果移动的正确，那么模式串里的子串p₀…p_k-1应该与子串的p_i-k…p_i-1匹配，这两个子串分别是p₀…p_i-1的长度为k的前缀和后缀，这样确定k的问题就变成了确定p₀…p_i-1的相等前缀和和后缀的长度。显然有k越小移动越远的结论。前面说的移动距离尽可能短。与之对应的是应该找的k是p₀…p_i-1的最长的相等前缀和后缀的长度，这样才能保证不会跳过可能的匹配。

上图中可以看出，如果p₀…p_i-1的最长相等前后缀的长度为k(0<k<i-1)，在p_i≠t_j的时候，模式串就应该右移i-k位。也就是说，应该把pnext[i]设置为k。

KMP的巧妙的递推算法

图二

现在假设对子串p₀…p_i-1p_i(也就是相对位置i)递推最长相等前后缀的长度，这时对pnext[i-1]已经计算出结果为k-1，比较p_i与p_k，有两种情况：

1. 如果p_i=p_k，那么对于i的最长相等前后缀的长度，比对i-1的最长相等前后缀的长度多1，此时应该将pnext[i]设置为k，然后考虑下一个字符。
2. 把前i-1个子串的最前相等前缀移动过来继续检查。

第二种情况并没有设置，只是继续检查。不难确定，移动过来检查是正确的。

已知pnext[0] = -1和直至pnext[i-1]的已有值求pnext[i]的算法：

1. 假设pnext[i-1] = k-1，如果p_i=p_k，那么最长前后缀长度就是k，将其计入pnext[i]，将i值加一后继续递推(循环)。
2. 如果p_i≠p_k，就将k设置为pnext[k]的值，(将k设置为pnext[k]，也就是转去考虑前一个更短的保证匹配的前缀，可以基于它继续检查)。
3. 如果k的值为-1，(这个值一定是来源于步骤2)，那么p₀…p_i的最长相同前后缀的长度就是0，设置pnext[i]=0，将i值加一后继续递推。

pnext表构造算法

基于上面的分析定义出来的算法：

def gen_next(p):
    i, k, pattern_len = 0, -1, len(p)
    pnext = [-1] * pattern_len  # 初始化数组元素全部为-1
    while i < pattern_len - 1:  # 生成下一个pnext元素值
        if k == -1 or p[i] == p[k]:
            i, k = i + 1, k + 1
            pnext[i] = k  # 设置pnext元素
        else:
            k = pnext[k]  # 退到更短相同前缀
    return pnext

　　函数刚开始时建立一个元素值全部为-1的表，循环中为下标为0之后的各元素赋值，具体处理完全是上面分析的情况，该算法的形式与前面KMP串匹配的主函数极为类似，算法分析情况可以照搬，结论是算法时间复杂度是O(m),m是模式串的长度。

算法改进

参考图一的状态1和状态2，由于匹配失败时有p_i≠t_j，设pnext[i]=k，如果发现p_i=p_k，那么也就一定有p_k≠t_j。所以这种情况下，实际模式串应该是右移到pnext[k](而不是仅右移到pnext[i])，下一步应该用p_next[k]与t_j比较，这一修改可以把模式串移动的更远，可能会提高效率。修改后的函数定义如下：

def gen_next(p):
    i, k, pattern_len = 0, -1, len(p)
    pnext = [-1] * pattern_len  # 初始化数组元素全部为-1
    while i < pattern_len - 1:  # 生成下一个pnext元素值
        if k == -1 or p[i] == p[k]:
            i, k = i + 1, k + 1
            if p[i] == p[k]:
                pnext[i] = pnext[k]
            else:
                pnext[i] = k  # 设置pnext元素
        else:
            k = pnext[k]  # 退到更短相同前缀
    return pnext

　　许多场景中需要用一个模式串反复在一个或者多个目标串里匹配，这种情况下，构造模式串里的工作只需要做一次，后面匹配中只需要简单反复使用，就是最适合KMP算法的场景。