算法学习:扩展KMP

发布于 / 算法学习 / 0 条评论

2019年8月5日下午,冰冷的雨滴击打着脆弱的窗户玻璃,机房里异常的安静,仿佛每个人都等待着一轮风暴。HDU的第五场多校赛已经过去了一半,距离吃饭只有两个半小时了,但我却没有一点开心的感觉。抬头,映入眼帘的就是一道魔鬼签到题目,和红色背景白色字体的“(-5)”字眼。机房的空调从来没有这么好使过,我甚至感到浑身寒冷,有几分想要颤抖身体。

比赛还是如期地结束了。这场比赛的这个签到题我还是没能做出来。是的,爆零了。我开始怀疑人生,怀疑自己存在的意义。挫败的我打开了题解,发现了这个叫做”扩展KMP“算法。虽然忧伤,但我还是尝试学习一下这个算法。于是……

题解传送门🚪

算法引入

假设现在有两个字符串,分别为 ST ,其中 S 为待匹配的串,T 为进行匹配的串,现在我需要知道 S 的每一位开始,分别可以匹配成功 T 串中从头开始的连续的多长子串。

举个例子,比如现在 S 为字符串AAAAABBBT 为字符串AAAAAC。我们定义数组extend[]为最终结果,其中 extend[i]S.\mathrm{substr}(i,n)S[i \cdots n-1]) 中与 T 匹配成功的最长相同前缀的长度。如本例中可得到如下表格:

i 0 1 2 3 4 5 6 7
S A A A A A B B B
extend[i] 5 4 3 2 1 0 0 0

如果使用暴力进行这个匹配过程的话,算法复杂度就达到了 O(m\times n),所以我们要用更好的算法来解决这个问题。这就是扩展 KMP 的任务。

算法思想

我们为何引入并使用next[]数组

暴力算法的问题就在于extend[]数组中的数据彼此之间是会有一些联系的,而暴力法并没有用上这些联系而直接进行了重新匹配。

假设我们现在匹配到了第 i 个位置,如下图:

其中图中 p 指从 S 的第 a 位开始与 T 匹配成功的最后一位的下一位,也就是说 S.\mathrm{substr}(a,p) = T.\mathrm{substr}(0,p-a)。如果从 i 开始的几位与 T 开头的几位相同,那么 extend[i] 的值就是这段距离的长度。所以我们引入 next[]数组来记录匹配串 T 中相同前缀部分的长度。比如对于AAAAAC,我们就可以得到以下列表:

i 0 1 2 3 4 5
T A A A A A C
next[i] 6 4 3 2 1 0

从头开始遍历 S,设当前遍历到了第 i 位,i + next[i -a ] 的值会有以下几种情况:

注意next[]数组

  1. i + next[i – a] < p

    说明这个时候的 i + next[i-a] 还在可控范围内。因为我们已经知道了 S.\mathrm{substr}(a, p)T.\mathrm{substr}(0, p-a) 相同,而 S[i + next[i -a]] 还在 S.\mathrm{substr}(a, p) 的范围内,所以这个时候 S.\mathrm{substr}(i, i + next[i – a])T.\mathrm{substr}(i – a, i – a + next[i – a]) 就可以成立,于是 S.\mathrm{substr}(i, i + next[i – a])T.\mathrm{substr}(0, next[i – a]) 就会成立,所以我们就可以知道 extend[i] 的值为 next[i – a]

  2. i + next[i – a] = p

    这种情况下,S[p]T[p – a] 不一定相同,T[p – i]T[p – a] 也不一定相同,但却有 T[p – a]S[p] 相同的情况,所以我们就直接对比 S[p]T[p – a] 及以后。然后得到 next[i] 的值。当我最后匹配直到 S[p + k]T[p+k-a] 相同,则可得到 next[i] 的值为 p + k – i。下一次再匹配时,只需要从 a = ip = p + k 开始就可以了。

  3. i + next[i – a] > p

    这种情况下我们就不能确定这上面的匹配方式相同了,所以我们就需要从 S[p]T[p – i] 开始匹配,具体做法同第 2 种情况。

获得next[]数组

其实这个就很简单了。next[]数组反映的即是 T 字符串中从第 i 位开始的内容与从第 0 位内容开始的最大相同前缀,所以其实只是把 T 与自己匹配跑了一编这个算法。

算法模板

int next[100];
int extend[100];
string S, T;
void getNext(){
    int m = T.length();
    // m:T的长度
    int a = 0, p = 0;
    next[0] = m;
    for (int i = 1; i < m; i++) {
        if (i >= p || i + next[i - a] >= p) {
            if (i >= p) p = i;
            while (p < m && T[p] == T[p - i])
                p++;
            next[i] = p - i;
            a = i;
        }
        else
            next[i] = next[i - a];
    }
}
void getExtend(){
    int n = S.length();
    int m = T.length();
    int a = 0, p = 0;
    getNext();
    for (int i = 0; i < n;i ++){
        if (i >= p || i + next[i - a] >= p) {
            // i >= p 的作用:举个典型例子,S 和 T 无一字符相同
            if (i >= p) p = i;
            while (p < n && p - i < m && S[p] == T[p - i])
                p++;
            extend[i] = p - i;
            a = i;
        }
        else
            extend[i] = next[i - a];
    }
}
转载原创文章请注明,转载自: KONGJUNE » 算法学习:扩展KMP
Not Comment Found