KMP 学习笔记

发表于 分类于

来源

在暴力匹配子串时，若不匹配，则跳回子串开头匹配主串的下一位。

会发现其实主串的部分位置已经遍历过了，这样重复的遍历导致了暴力算法并不优秀。

我们可以让子串跳过一部分主串，以达到更高的效率。

实现

我们定义一个数组 $nx$ ，表示如果子串在第 $i$ 位失配，应该把子串向前移到 $nx_i$ 位继续匹配。

设子串为 $b$，$nx_i$ 的值为 $j$，满足 $b_0$$b_j$ 与 $b_{i-j+1}$$b_i$ 相等，这样就可以减少重复匹配。

于是我们遍历主串，同时匹配子串，如果失配就跳，成功匹配就匹配子串下一位。

如果子串匹配结束，那么说明找到了一个子串，记录开头位置并继续匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void kmp()
{
    int j = 0;

    for (int i = 0; i < lena; i++) {
        while (j && a[i] != b[j])
            j = nx[j];
        if (a[i] == b[j])
            j++;
        if (j == lenb)
            printf("%d\n", i - lenb + 2);
    }
    return;
}

如何求得 $nx$ 呢？

我们可以将子串与自己匹配，在过程中也利用了已经求好的 $nx$ 值。

显然 $nx_0=0$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void init()
{
    lena = a.size();
    lenb = b.size();
    int j = 0;
    for (int i = 1; i < lenb; i++) {
        while (j && b[i] != b[j])
            j = nx[j];
        if (b[i] == b[j])
            j++;
        nx[i + 1] = j;
    }
    return;
}

可以看出和匹配几乎是一模一样的。

应用

求给定子串出现位置

求最长重复子串

即 $nx$ 的最大值

求主串最多由多少个相同子串不重叠连接组成（复读）

子串长度 $k=len-nx_{len-1}$。

若 $k|len$ 则子串个数 $n=len/k$，否则 $n=1$。