我所理解的KMP算法

KMP 取自Knuth-Morris-Pratt 三人,一种字符串查找算法。

对于加快字符串的匹配查找,一般会对字符串做预处理然后再进行匹配查找,一种是对源串做预处理,另一种是对目标串(模式串)做预处理;KMP算法则是后者。

拿模式串在源串中进行比较匹配,当源串指针与模式串指针对应值不匹配时,源串指针无需向前回溯重头开始,仅通过移动模式串指针从而完成匹配,这是KMP的算法逻辑,那模式串指针该如何移动呢?模式串指针与源串已匹配到某一位置而无法继续,根据已有的匹配情况,需要跳转到下一位置继续匹配,这个跳转实质就是该模式串的DFA(确定有限状态自动机),因此对模式串的预处理就是构造DFA,实现状态转移,构造DFA的过程实质是寻找该模式串的自匹配程度,引申下就是计算该模式串的特征向量,在具体的算法分析中实际就是next数组,该数组代表了模式串的自匹配程度,即对应的特征向量。

如何用通俗的语言解释和简单的方法计算该特征向量呢?也就是该如何求next数组?
大部头算法导论给出了next数组定义如下:kmp next array
用通俗的语言解释上述定义就是:
模式串当前子串对应的next值实质是该子串对应的前缀数组与后缀数组的最长公共串的长度,也即待比较的前缀下一字符在模式串数组中的对应索引位置值,也就是模式串当前待匹配位置应该与哪个位置继续比较,这个“哪个位置”就是已匹配的next值。
举例来看pattern: abababca,j=4时,pattern当前子串为ababa,则前缀数组和后缀数组分别如下(均不包含自身):
kmp-prefix-suffix由前缀数组和后缀数组可知,最长公共串为aba,长度为3,则next[4]为3。据此可计算整个pattern串的next数组对应如下:
example-next-array
那该如何实现呢?计算pattern串的next数组的过程也就是计算模式串自匹配的过程,每一步计算要基于已有的匹配得出,仍然以开始计算j=4时为例,基于已有匹配j=3时next[3]=2,说明存在j=3前缀长度为2与j=3后缀长度为2相等,若前缀下一字符与后缀后一字符相等,则next[3]+1的值即为next[4]的值。需要注意的是,next值为长度值从前缀方向看实际也是下一字符的数组索引位置值,已有匹配的后缀后一字符即当前正在计算的待匹配字符,所以若相等必定长度加1;若不等,则更新已有匹配为前缀方向不匹配位置的前一位置(实质在向前回溯),拿该位置的next值继续比较,若仍然不匹配相等,则可能很快就到了模式串的起始位置。
上面的算法讲解还是比较清晰易懂的,如果搜索网文会发现大量的云里雾里绕来绕去,关键部分一笔掠过。现在我们拿出next数组的实现代码吧~参考如下,思想和上述讲解是完全一致的~

void GetNext(string pattern, int *next)
{
    i = 0; j = -1;
    while (i < pattern.length()) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (j == -1 || pattern[i] == pattern[j]) {
            ++ j;
        }
        next[i] = j;
        ++ i;
    }
} 

refer:
1. https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注