kmp


KMP 算法是一种字符串匹配算法,可以在 O(n+m) 的时间复杂度内实现两个字符串的匹配。

在学习 KMP 算法之前,先来看看朴素的字符串匹配算法

1. 字符串匹配问题

字符串匹配问题是这样一个问题:给你一个字符串 S,再给你一个字符串 P (又称为模式串),需要你判断 P 是否在 S 中出现,在哪里出现。

最朴素的暴力做法就是将 P 作为一把“标尺”,不断的移动并进行比较,直到找到匹配的位置,如下图:

这种算法的优点十分明显,那就是简单,简单到小学生都会

缺点也很明显,效率低下,时间复杂度为 O(n * m)

光上面这个例子还不能引出 KMP 算法的核心思想,我们再来看一个例子

暴力算法依旧可以解决字符串匹配问题,但是从这个例子我们能发现更多细节

图中可以看到,字符串匹配在 p[5] 时失配,这时候我们还需要按照暴力算法,每次将 P 移动一位吗?

移动一位后,s[1] != p[0],不匹配, 继续移动

直到从 s[3] 开始,s[3:5](意思为下标在[3,5)的子串)= p[0:2]

这时候才刚好完成部分匹配,接下来才能开始继续比较后面的字符


如果你尝试了一步步移动模式串 P,你会发现你始终在将 S 的某一部分,与 P 的开头一部分进行比较。而这开头的一部分子串称为前缀,模式串 P 的前缀

那么 S 中我们比较的是哪一部分呢?

从过程而言,S 中比较的是任何一部分。但从结果而言,S 中需要比较的仅仅是末尾部分,也就是后缀

结合图片再来理解理解:

假设我们对主串 S 的匹配工作已经进行到了子串 s[i:j+1] 部分

这时候 s[j] 失配了,我们需要将模式串 P 向后移动

由于对 S 的遍历只到达了 j 的位置,所以对于 s[j] 之后的字符都是未知的,并且此时的目标是找到能让 s[j] 匹配的位置(如果存在的话)

随着模式串 P 的移动,会出现以下三种情况(下图任何长度等数据皆为示例)

  1. P 的前缀s[i:j] 中的一部分匹配,而后面不匹配

  1. P 的前缀s[i:j]后缀相匹配

  1. s[i:j] 无法找到合适的位置,P 从 j 开始重新匹配

情况 3 不用多说,是一种非常普遍的现象

情况 1 和情况 2 中,由于 j 往后的字符还没遍历,都处于未知状态,所以对于标尺 P 来说,最合适的位置就是它的一部分前缀已经匹配的位置。情况 1 显然不可能,虽然匹配了一部分前缀,但是后面的已知部分不匹配,所以这种情况可以跳过。我们真正需要找的位置是情况 2,也就是 s[i:j+1] 的后缀与 P 的前缀相同

知道了原理之后,怎么实现呢?如何跳过中间过程中 n 个情况 1,直接到达情况 2 ?


由于 s[i:j] 已经与 p[0:5] 匹配,所以“ s[i:j] 的后缀等于 P 的前缀”这句条件可以转化为,p[0:5] 中后缀等于前缀的部分,同时为了覆盖尽可能多的情况,也就是标尺移动的尽量要少,所以取最长的相等长度

使用通用的语言表达:

当 P 失配时,我们要在 P 的已匹配部分中找到 后缀等于前缀 的最大子串长度,并将 P 移动到相应位置继续进行匹配

例如 P 为 ABCABD 当第六个字符失配时,前五个字符 ABCAB 是匹配的,这时候后缀等于前缀的最大长度为 2 (”AB”)

2. next 数组

next 数组是对于模式串 P 而言的,next[i] 表示 P[0] ~ P[i] 这个子串中 前k个字符后k个字符 相等的最大的 k。同时由于数组下标从 0 开始,所以 next[i] 又可以表示为失配后跳转到的下一个下标,从这个位置继续开始匹配。

image-20220804103218043

对于上图中的 next 数组该如何构建呢?

显然,对于第二次出现的 A 或 B,由于P[i] == P[next[i - 1]],所以 next[i] = next[i - 1] + 1

当然,这只适用于部分情况,而更多普遍的情况需要更复杂的算法


我们需要比较的是前缀与后缀,所以需要两个指针,now 与 x

image-20220804104346527

图中 next[x] 该是多少呢,反正不可能是 6,难道是 0 吗?

你应该也看出来了,前缀 “ABC” 与后缀 “ABC” 相同,所以 next[x] = 3

从算法的角度来看,虽然 P[now] != P[x] ,但是他们前面的部分是相同的,也就是图中的绿色部分,我们将绿色部分单独看成一个模式串,而 P[0:now]部分的 next 数组已经处理好了,所以绿色部分我们可以很容易找到最大长度的 k,也就是 next[now - 1]

所以我们从 next[now - 1]的位置继续匹配,发现 P[x] = P[next[now - 1]],所以 next[x] = next[now - 1] + 1

如果他俩不相等,那么我们继续这样划分子串,直到相等或者下标为0

下面贴上代码


int next[n];

void buildNext() {
    int now = 0, x = 1;
    while (x < n) {
        if (p[now] == p[x]) {
            next[x] = next[now] + 1;
            now++;
            x++;
        } else if (now > 0) {
            now = next[now - 1];
        } else {
            next[x] = 0;
            x++;
        }
    }
}

3. 实际应用

贴一个简单的字符串匹配代码

string s, p;
// 省略输入部分
int next[p.size()];
// 省略next数组构造

int tar = 0; // 主串中匹配的位置
int pos = 0; // 模式串中匹配的位置
while (tar < s.size()) { // 查找s中所有匹配的位置
    if (s[tar] == p[pos]) {
        tar++;
        pos++;
    } else if (pos > 0) {
        pos = next[pos - 1];
    } else {
        tar++;
    }
    
    if (pos == p.size()) { // 匹配成功
        cout << tar - pos + 1 << endl; // 输出匹配的起始位置
        pos = next[pos - 1]; // 移动标尺,继续寻找下个匹配
    }
}

参考文章


文章作者: ❤纱雾
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ❤纱雾 !
评论
  目录