KMP 算法与 border 浅记
![](https://s2.loli.net/2023/09/15/mLYDw6nxO9RaEke.jpg)
终于完全明白了困扰多年的 KMP 算法,果然从 border 理论理解才是最好的。
因此写下本文,供自己复习。
border
首先给出 \(\text{border}\) 的定义:在字符串 \(S\) 中,最长的真公共前后缀。
显然,\(\text{border}\) 的 \(\text{border}\) 也是 \(S\) 的一个 \(\text{border}\)。
我们定义 \(\text{nxt}[i]\) 为 \(S[1\dots i]\) 的 \(\text{border}\),考虑如何快速求 \(\text{nxt}\)。
假设我们现在已知 \(\text{nxt}[1\dots n]\),想要求出 \(\text{nxt}[n+1]\)。
考虑 \(S[n+1]\) 和 \(S[\text{nxt}[n]+1]\) 是否匹配。如果匹配,那么显然。 \(\text{nxt}[n+1]=\text{nxt}[n]+1\),否则我们继续考虑它是否可以和 \(\text{nxt}[\text{nxt}[n]]\) 匹配。我们一直匹配到成功即可。
这样可以均摊 \(O(n)\) 求出 \(\text{nxt}\)。
1 | S = " " + S; |
KMP
\(\text{KMP}\) 是用来快速匹配字符串的算法。
给定模式串 \(S\),文本串 \(T\),求 \(S\) 在 \(T\) 中所有匹配。
记 \(S\) 长度为 \(s\),\(T\) 长度为 \(t\)。
我们将 \(S\) 和 \(\#\) 和 \(T\) 拼在一起,形成了 \(S\#T\) 的新字符串。我们求出来这个字符串的 \(\text{nxt}\)。
之后我们从 \(s+1\) 开始(即从 \(T\) 开始)遍历 \(\text{nxt}\)。如果 \(\text{nxt}[i] = s\),那么这是一个成功的匹配。
时间复杂度 \(O(n+m)\)。
- 标题: KMP 算法与 border 浅记
- 作者: 夏佑 | XiaU
- 创建于 : 2023-08-01 00:00:00
- 更新于 : 2023-10-03 09:59:41
- 链接: https://summace.cc/KMP/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。