数据结构｜KMP算法

KMP是一种高效的串查找算法，其主要特点有是不回溯主串，特别适合如边传边找的网络传输场景。

为了做到这一点，KMP算法要提前处理模式串，目标是知道在匹配失败时，如何回退模式串指针。当匹配发生失配时，我们不想像朴素算法那样，把模式串完全移回开头，而是利用已经匹配过的信息，把它“智能”地向右滑动一段距离。

你可以把这个回溯过程想象成模式串的滑动，如果匹配失败，就向右滑动模式串，到模式串的最长前缀和当前主串位置point前的最大后缀对齐，由于在此之前主串当前位置前已经和模式串当前位置前匹配上，所以其实可以直接使用模式串的数据，而不需要回退主串。

Example：

主串 ABABABCA 模式串 ABABX

alt text

也可以看看下面这个动画演示：

所以实际我们只要提前计算好在每个位置匹配失败时会回落到什么位置就行了。这个东西就是next数组，保存在匹配失败时模式串跳回什么位置。

计算next数组很简单，就是拿一个point在模式串上扫描，假设在这个位置匹配失败时，模式串会回落到哪里，就是找point前到最长公共前后缀。

alt text

我们这里采用以0为开头的标记。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void get_next(const std::string s, int next[]) {
    next[0] = -1;//第0个元素不能再回退了
    int i = 0, j = -1;
    while (i < s.length() -1) {
        if (j == -1 || s[i] == s[j]) { 
            //如果前缀在-1了（在串外面了，再不济也要回退到第一个吧）
            //或者现在前缀和后缀还是匹配着的
            i++;
            j++; //就各向后挪
            next[i] = j; //然后记录这个结果。注意这里i和j都已经被+1过了
        } else {
            //否则，前后缀不匹配了
            j = next[j]; //直接用已经创建好的部分数组回滚再试
        }
    }
}

但是我们发现，如果要跳回去的那个目标和现在失败的位置是一样的，那必然还是失败，会导致多次跳跃。那我们为什么不在生成next数组时就帮他跳好呢？

于是便出现了nextval这个优化的版本：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void get_nextval(const std::string s, int nextval[]) {
    int i = 0;
    nextval[0] = -1;
    int j = -1;
    while (i < s.length()-1) {
        if (j == -1 || s[i] == s[j]) {
            i++;
            j++;
            if (s[i] != s[j]) {
                nextval[i] = j;
            } else { //如果必然失败，就帮他跳好
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
}

也可以看看下面这个动画演示：

数据结构｜KMP算法

字符串匹配KMP算法介绍

KMP 匹配演示

Nextval 生成