其实之前学过好多次了,都没有学懂……
现在学懂了(写一篇博客免得忘掉)
Part1. 字符串匹配问题
在这个问题中,给出两个字符串 $S,T$,要求回答 $T$ 是否是 $S$ 的一个子串。
关于 $S,T$,在字符串匹配问题中,$S$ 称为主串,$T$ 称为模式串。那么我们就是要在主串中找模式串。
Part2. Brute-Force
顾名思义,暴力算法。设主串 $S$ 长度为 $n$,模式串 $T$ 长度为 $m$。那么我们暴力地枚举每个 $S$ 的子串(其实就是枚举每个子串的开始位置),复杂度 $O(n)$;然后对于每个子串,暴力检测子串是否与 $T$ 相同,复杂度 $O(m)$。
所以复杂度为 $O(nm)$。显然太慢了,尤其是主串 $n$ 比较大的时候。
Part3. KMP 算法
“KMP” 是算法提出者(不止一个人,但是我忘了 awa)的名字缩写。
Part3/1. 算法思路
首先分析 Brute-Force 的缺陷:完全没有利用上一次匹配得到的信息,每一次匹配要将模式串的指针和主串的指针都回溯到起始位置。
相反,KMP 就尽可能地利用了已有的匹配信息,并且不再回溯主串的指针,而是把 模式串向右移动。而且模式串向右移动并不是简单的右移一位,而是移动到尽可能远的、可能匹配的位置。
下面这种情况,$S_{i-j+1\to i-1}$ 和 $T_{0\to j-1}$ 已经匹配,但是在 $S_i,T_j$ 这个位置失配,就像下图这样:
那么我们考虑把 T 向右移动,假设移动到 $S_i$ 对应 $T_k$ 时,$S_{i-k\to i-1}$ 和 $T_{0\to k}$ 匹配了。
(并不知道 $S_i$ 和 $T_k$ 是否会匹配)说明 $k$ 是下一个可能匹配的位置。于是我们把 $T$ 的指针移动到 $k$ 继续匹配。
在 KMP 中,当 k 和 j 满足上述关系时,定义 fail
指针 $fail(j)=k$。
Part3/2. fail
指针的性质
考虑 $k$ 和 $j$ 满足什么条件,$fail(j)=k$。
框起来的这部分一定完全一样,不然 $T_{0\to k-1}$ 不可能和 $S_{i-k\to i-1}$ 匹配。也就是 $T_{0\to k-1}=T_{j-k\to j-1}$,所以 fail
指针其实和主串 $S$ 没有关系,只跟 $T$ 本身相关。
根据定义,以及算法的特殊设计:
如果 $i=0$,即模式串的开头就失配了,就只有把模式串向右移一位了,于是 $fail(0)=-1$。如果存在这样的 $k$,就可以将模式串向右移动到尽可能远的位置(所以是取 $\max$)。如果不存在这样的 $k$,就只有把模式串挪到开头,尝试匹配。
Part3/3. KMP 主函数
有了 fail
指针,我们就可以不再回溯主串的指针,而是将模式串向右挪到 $fail()$ 的位置。
1 | int KMP(){ |
Part3/4. 求 fail
指针
最难计算的显然是 $fail(j)=\max\{k|T_{0\to k-1}=T_{j-k\to j-1}\}$ 的情况嘛。
假如我们已经计算出来了 $fail(j)$,怎样递推的求出 $fail(j+1)$?
- 如果 $T_{fail(j)}=T_{j}$,那么就可以向后匹配一位,也就是 $fail(j+1)=fail(j)+1$;
- 否则就相当于把 $T$ 同时作为模式串、主串进行匹配,在 $T_{fail(j)}$ 和 $T_j$ 位置失配,照样采用 KMP 的思想,将 j 跳回 $fail(j)$ 的位置,继续匹配,直到匹配成功或者退回到起始位置;
1 | void GainFail(){ |
Part4. 不如来手玩一下?
标号: 0 1 2 3 4 5 6 7
模式串:b c a b c a a b
计算过程:
- $fail(0)=-1,fail(1)=0$;此时两个指针 $i=1,j=0$
- $T_i\not=T_j$,$j$ 退回到 $fail(j)=0$,仍未匹配,退回到 $fail(j)=-1$;回到起始位置 $fail(i+1)=j+1=0$;此时 $i=2,j=0$
- $T_i\not=T_j$,$j$ 退回到 $fail(j)=-1$,回到起始位置 $fail(i+1)=j+1=0$;此时 $i=3,j=0$
- $T_i=T_j$,匹配,$fail(i+1)=j+1=1$;此时 $i=4,j=1$
- $T_i=T_j$,匹配,$fail(i+1)=j+1=2$;此时 $i=5,j=2$
- $T_i=T_j$,匹配,$fail(i+1)=j+1=3$;此时 $i=6,j=3$
- $T_i\not=T_j$,$j$ 退回到 $fail(j)=0$ 仍未匹配,$j$ 退回到 $fail(j)=-1$;回到起始位置,$fail(i+1)=0$;此时 $i=7,j=0$
- $T_i=T_j$,匹配,$fail(i+1)=j+1=1$
结果是
fail:-1 0 0 0 1 2 3 0 1
Part5. 源代码
> 模板题 - 洛谷
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
字符串好快乐啊~ (打脸)