算法学习:扩展KMP

算法学习:扩展KMP

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

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

题解传送门🚪

算法引入

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

举个例子,比如现在 $S$ 为字符串AAAAABBB, $T$ 为字符串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$ 个位置,如下图:

1565080573726

其中图中 $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$

    1565095531149

    说明这个时候的 $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$

    1565095544744

    这种情况下,$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 = i$、$p = p + k$ 开始就可以了。

  3. $i + next[i - a] > p$

    1565097429456

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

获得next[]数组

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

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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];
}
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×