🍕 KMP 算法
KMP 主过程
【题意】 现在有两个字符串, 文本字符串 txt 和模版字符串 pat , 要求在 txt 是找出 pat 出现的下标。 没有则返回 -1
暴力搜索: 遍历 txt, 对每一个字符都判断, 以这个字符开头的字符串, 能否匹配出 pat。 暴力搜索的时间复杂度是 O(N*M), N 是 txt 长度, M 是 pat 长度。
KMP 需要借助一个 next 数组, 我们先不讲 next 数组的具体实现, 先明白 next 数组的内容就行。
了解 next 数组的构成
【字符串的最大相同真前后缀长度】: 比如 （真前后缀概念类比真子集）
- 字符串 aaaaa 的最大相同真前后缀长度
- 长度 4 时, 前缀 aaaa, 后缀 aaaa, 故最大相同真前后缀长度 4。 （不能是 5, 因为字符串的最大相同真前后缀长度 不可能等于字符串本身长度）
- 字符串 aabaab 的最大相等前后缀长度
- 长度 1 时, 真前缀 a, 真后缀 b, 不相同
- 长度 2 时, 真前缀 aa, 真后缀 ab, 不相同
- 长度 3 时, 真前缀 aab, 真后缀 aab, 相同
- 长度 4 时, 真前缀 aaba, 真后缀 baab, 不相同
- 长度 5 时, 真前缀 aabaa, 真后缀 abaab, 不相同
- 故最大相等前后缀长度为 3
next 数组就是用来存储 pat 字符串的每个字符左侧子串(不包含该字符本身)的 最大相同真前后缀长度, 比如:
pat为 aabaab- 下标 0 的字符 a, 左侧是空字符串, 没有 最大相同真前后缀长度, 故人为给定一个值, 比如 -1
- 下标 1 的字符 a, 左侧只有长度为 1 的子串
a, 最大相同真前后缀长度 始终是0 - 下标 2 的字符 b, 左侧子串为
aa, 最大相同真前后缀长度 为1 - 下标 3 的字符 a, 左侧子串为
aab, 最大相同真前后缀长度 为0 - 下标 4 的字符 a, 左侧子串为
aaba, 最大相同真前后缀长度 为1 - 下标 5 的字符 b, 左侧子串为
aabaa, 最大相同真前后缀长度 为2
KMP 主过程讲解
在 txt 中搜索 pat 字符串的过程中, 用到两个指针:
t指针指向txtp指针指向pat
首先, 比对 t 指针指向的值是否等于 p 指针指向的值。 如果不相等, 则 t 指针往前走
txt: a b c e o e S F c e o e S ..........
↑
pat: c e o e S F c e o e F ......
↑
txt: a b c e o e S F c e o e S ..........
↑
pat: c e o e S F c e o e F ......
↑- 如果相等, 则
t和p'指针一起往前走, 继续比对
txt: ....c e o e S F c e o e S ..........
↑
pat: c e o e S F c e o e F ......
↑
txt: ....c e o e S F c e o e S ..........
↑
pat: c e o e S F c e o e F ......
↑
txt: ....c e o e S F c e o e S ..........
↑
pat: c e o e S F c e o e F ......
↑
...
...
...
txt: ....c e o e S F c e o e S ..........
↑
pat: c e o e S F c e o e F ......
↑如果比对成功, 则直接找到, 但如果比对失败, t 指针不要动!
这就是和暴力搜索不一样的地方, 同时也是 KMP 速度快的地方。 暴力搜索慢就慢在:
- 如果此时比对不成功,
t指针会直接回到 第一次匹配成功的下一个位置, 继续匹配。 - 同时
p指针也会回到开头重新匹配。
但实际上, t 指针在匹配失败的过程中, 肯定是有得到一些 "信息" 的, 暴力搜索完全忽视了这些 "信息"。 但是 KMP 利用了这些信息, 这些信息就存储在 next 数组中
首先看, 当前的 p 指针停留在 F 处, 根据 next 数组, 我们可以获取 F 左侧子串的 最大相同真前后缀长度为 4。 此时 next[p] = 4, 相同的前缀和后缀如下所示
txt: ....c e o e S F c e o e S ..........
↑
pat: c e o e S F c e o e F ......
└─────┘ └─────┘ ↑同时, 因为 t 和 p 是通过比对成功才走到现在这个位置的, 所以我们可以保证, 在 txt 字符串中, 同样也有这个子串 ceoe
txt: ....c e o e S F c e o e S ..........
└─────┘ └─────┘ ↑
pat: c e o e S F c e o e F ......
└─────┘ └─────┘ ↑虽然我们这里举的是具体的例子, 但其实无论具体的值是什么, 只要 p 指针当前位置的 next[p] 值不为 0, 就一定说明存在四段相同的子串。
txt: ....x.....x ... x ... x ? ...... 问号 ? 表示未知符号
└─────┘ └─────┘ ↑
pat: x.....x ... x ... x ? ...... 问号 ? 表示未知符号, 不等于上面的问号
└─────┘ └─────┘ ↑
\ /
任意长度子串, 并且一定相等现在请你以 "懒人" 的角度思考问题, 你已经在 txt 上从位置 a 比对到位置 b 了, 见下图
a a+1---------------> b
txt: ....x.....x ... x ... x ? ......
└─────┘ └─────┘ ↑
t
pat: x.....x ... x ... x ? ......
└─────┘ └─────┘ ↑
c p然后你突然发现 t 和 p (理解为你的两个手指) 指向的值不同了(上图中的两个问号是不相同的)。 同时你知道位置 a 到位置 b 有两段内容是一样的, 并且 txt 的 a 到 b 范围和 pat 的 a 到 b 范围是一样的, 作为一个 "懒人" , 你难道还想要把 p 回退到 c 位置(见上图), 把 t 回退到 a 的下一个位置 a+1 继续重新比对吗?
肯定不会的! 也许你此时还不知道怎么做, 但如果你是自己尝试一个一个数比对的话, 你肯定会觉得此时应该有办法 "偷懒"。 你的 t 已经走到 b 位置了, 那就说明 b 位置肯定不是 pat 的尾巴。 但是你又无法保证 a 到 b 中没有 pat 的头, 所以你陷入就纠结。
这个时候, 你想到了 txt 和 pat 中相同的部分, 即图中的 4 块内容 甲, 乙, 丙, 丁 是相同的
txt: ....x.....x ... x ... x ? ......
└─────┘ └─────┘ ↑
甲 乙
pat: x.....x ... x ... x ? ......
└─────┘ └─────┘ ↑
丙 丁现在的情况是, 甲 对 丙, 乙 对 丁 肯定是行不通的。 但你可以再看看 乙 对 丙 行不行得通呀! 如下图:
a --------------> b
txt: ....x.....x ... x ... x ? ......
└─────┘ └─────┘ ↑
甲 乙
pat: x.....x ... x ... x ? ......
└─────┘ ↑ └─────┘
丙 丁这个时候, 你就会发现:
- 我们的
t指针不需要动了! - 我们的
p指针不用完全回到开头了!
因为我们能保证 乙 和 丙 的内容是一样的, 这个信息来自我们上一次匹配失败的过程: 虽然匹配失败了, 但是我们能保证 a 到 b 范围内是和 pat 的前缀吻合的。 (其实到这里 KMP 算法就已经讲完了。)
现在让我们从新的位置继续比对, 把图中的无用信息擦掉, 会发现图变得跟前面的很相似
txt: ....x ... x ? ......
└─────┘ ↑
乙
pat: x.....x ?.........................
└─────┘ ↑
丙这不就是前面的, 两个指针指向的内容一样然后一起加加的情况嘛! 那后续的过程就简单了, 相同就一起走, 如果不同了, 就再看看 next 数组。 总而言之:
t指针肯定不会往回走的p指针不好说, 如果在next数组中查到的值不是 0 的话, 那就可以回退一点点。
当再一次匹配不成功, 并且 p 指针对应的 next[p] 等于 0时, 就说明 当前的 t 和 s 前面肯定没有可以匹配成功的了。 于是 p 指针只能回到开头, t 指针则向前一步继续匹配。
如此反复,
- 如果匹配成功, 最后的下标
p大小就会等于pat的数组长度 - 如果匹配失败, 那就是
p大小不等于pat的数组长度, 同时t指针走到头了。
KMP 的过程就是这么简单! 不懂的话, 再看看下面的代码, 就懂了。
KMP 主过程代码
【老师版本】
// 返回 txt_str 中 pat_str 第一次出现的下标
int getIndexOf(String txt_str, String pat_str) {
// 边界条件不要忘记: 字符串不能空, 不能查找空串, 查找的串不能比搜索区域还大。
if (txt_str == null || pat_str == null || pat_str.length() < 1 || txt_str.length() < pat_str.length()) {
return -1;
}
char[] txt = txt_str.toCharArray();
char[] pat = pat_str.toCharArray();
int t = 0;
int p = 0;
int[] next = getNextArray(pat); // O(M) 先不用管它怎么实现的, 总之就是拿到了 pat 的 next 数组。
// KMP 主过程
while (t < txt.length && p < pat.length) { // O(N)
if (txt[t] == pat[p]) { // p t 指针相同, 就一起加加
t++;
p++;
} else if (p == 0) { // 等效于 next[p] == -1, 这就是为什么前面说 第一个元素的 next 值无所谓的原因
t++; // 确保 t 前不可能匹配到 pat 的头了。
} else {
p = next[p]; // p 不需要直接回退到 0, 同时 t 也不需要动! KMP 的精髓就是这行代码。
}
}
return p == pat.length ? t - p : -1;
}【py版本, 已验证】:
def strStr(txt: str, pat: str) -> int:
if len(txt) < len(pat):
return -1
t, p = 0, 0
_next = self.getNextArr(pat)
while t < len(txt) and p < len(pat):
if txt[t] == pat[p]:
t += 1
p += 1
elif p > 0:
p = _next[p]
else :
t += 1
return t-p if p == len(pat) else -1证明时间复杂度 O(N)
证明 KMP 代码中的 while 循环是 O(N) 级别的:
- 首先, 证明复杂度的难点在于, 虽然 t 是不会变小的, 但是 p 会变小, 所以一时难以知道循环会跑多少轮次。
- 利用两个变量
t和t-p,t的最大值是 N, N 表示txt的长度t-p的最大值也是 N, 因为p虽然会减小, 但最小值是 0
- 现在分析循环中的三个分支
- 分支一,
t和p都增加, 故t增加,t-p不变 - 分支二,
t增加,p不变, 故t增加,t-p增加 - 分支三,
p减小,t不变, 故t不变,t-p增加
- 分支一,
- 每次循环都会执行其中一个分支, 而不管是哪个分支,
t和t-p肯定有一个值在变大 - 现在就简单了, 之前是因为 一个变大一个变小, 我们难以知道循环会跑多要轮次。
- 但现在两个变量
t和t-p都不可能减小, 所以就容易分析了。 - 每次循环,
t和t-p一定有一个值在增加。 - 而
t最大是 N, 所以一旦t增加到 N 后,t就不可能变了。 此时循环跑了 N 轮次 - 但
t和t-p有一定要有一个值在增加, 那么就只可能是t-p在增加, 也就是只可能是p在减小。 - 但
p最多又能减小到多少呢?p最大值是 M (M 表示pat长度), 最小值是 0。 - 也就是说,
p最多能够从 M 一直减小到 0, 此时循环跑了 M 轮次。 - 所以, 循环最多跑 N+M 轮次, 考虑极端情况, M 等于 N, 那么此时也才 2N 级别
- 综上, 时间复杂度是
O(N)。
求取 next 数组 (附证明)
求取某一字符串 str 的 next 数组过程如下:
情况1: 长度变长
next[x], 表示的是从位置 0 到位置 x (不包含位置 x)这一个子串, 它的最大相同真前后缀的长度。
求这段子串的最大相同真前后缀长度
┌────────────────────┐
0...................x-1 x说明: 所谓真前缀, 真后缀, 类似于子集和真子集。 真前缀不能等于字符串本身, 比如字符串
abc, 前缀可能是a,ab,abc, 但是真前缀只可能是a,ab, 不可能是abc同理, 真后缀也是一样, 字符串abc, 它的后缀可能是c,bc,abc, 但真后缀只可能是c,bc, 不可能是abc。
因为 "最大相同真前后缀的长度" 写起来太长了, 所以后面直接使用 next[x] 代表位置 x (不包含位置 x) 左侧字符串的 "最大相同真前后缀的长度"。
我们想要求取 next[j] 的值, 我们需要先查看 next[j-1] 的值。 假设 next[j-1] = y, 则说明 j-1 位置的左侧字符串的真前缀是 0..... y-1, 真后缀是 .....j-2。 如下:
0............. y-1 y .... 后面子串写到下面了, 这样方便分析, 同时也表示了 y 位置不可能是 j-1 位置, 即都是真前缀和真后缀。
↕ ↕ ?
.............. j-2 j-1 j说明:
next[j-1] = y,y是长度, 而我们的位置是从0开始的, 所以表示长度为y的字符串会写成0......y-1。 如果字符串0..... y-1以0开头, 说明该字符串是真前缀, 其的下标范围是[0, y-1]。 如果字符串前面没有0, 比如..... j-1, 则该字符串表示的是真后缀, 具体下标范围不考虑, 因为它不影响我们理解, 只需要知道真后缀开头位置的值肯定和位置0的值相同。
我们记字符串 str 上某位置的字符为 str[某位置], 比如 y 位置上的字符记为 str[y], j-1 位置上的字符记为 str[j-1] 当 str[y] 等于 str[j-1] 时, 会出现 真前缀 0.....y 等于 真后缀 .....j-1, 如下:
0............. y-1 y ....
↕ ↕ ↕
.............. j-2 j-1 j所以, 此时的 next[j] 就等于子串 0.....y 的长度, 即 next[j] = y+1。
问题来了, next[j] 的值还可能更大吗? 答案是不可能!, 下面给出证明
证明: next[j] - next[j-1] 不可能大于 1
要证明 next[j] 不可能有更大的值, 相当于证明: next[j] - next[j-1] 不可能大于等于 2。
我们使用反证法:
- 首先要给出前提:
next[j-1] = y。 - 然后要给出假设:
next[j] = e, 其中e >= y+2 - 最后, 以这两个作为条件, 进行推导, 看看是否有会冲突, 如果出现冲突, 则说明假设不成立, 反之假设成立。
根据条件 next[j] = e, 得到真前缀 0.....e-1 和 真后缀 .....j-1 相等 。 又根据 e >= y+2, 我们可以画出字符串如下:
0............. y-1 ... e-1 .... y-1 和 e-1 差值大于 1, 即中间存在新的位置, 故在中间添加 ... 作为标识
↕ ↕
...................... j-1 j既然真前缀 0.....e-1 和真后缀 .....j-1 相等, 那说明真前缀 0.....e-2 和真后缀 .....j-2 肯定也是相等的:
0................ e-2 e-1 ....
↕ ↕ ↕
................. j-2 j-1 j也就是说, 对于位置 j-1 来说, 它的 next[j-1] 可以等于真前缀 0.....e-2 的长度, 即 next[j-1] = e-1 。 关键来了, 我们的前提是 next[j-1] = y, 而你的假设求出的 next[j-1] = e-1, 并且假设中又说了 e >= y+2。 也就是说, 根据假设, next[j-1] 存在更长的相同真前后缀, 这和我们的前提冲突, 故假设不成立, 从而证明 next[j] - next[j-1] 不可能大于 1。
情况2: 长度变短
前面讨论的情况 1 , 是 str[y] 等于 str[j-1] 的情况, 此时 next[j] 会等于 next[j-1] + 1, 如下所示:
0............. y-1 y ....
↕ ↕ ↕
.............. j-2 j-1 j并且我们证明了 next[j-1] + 1 就是 next[j] 的最大值。 所以, 当 str[y] 不等于 str[j-1] 时, next[j] 只会变短。 这个时候, 我们又该怎么做呢?
通过前面情况 1 的讲解, 我们应该发现了一种很方便的做法： 在前面已经求出的 next[?] 的基础上, 只需再比较 str[?] 是否等于 str[j-1] 就可以了。
注意: 此时不要去想太多前面的 next 是怎么求的, 记住他们已经求出来了, 并且求对了就行。 如果现在就开始纠结前面的 next 怎么求的, 那么你的学习效率会很低。 相反, 等到后面讲解完了, 你再思考, 那么你就会恍然大悟 (虽然正常来说, 学算法都学到 KMP 了, 应该是有这种思维的。)
这种做法很方便, 但问题在于, 我们如何确定下一个 "? 位置" 呢?
0............. ?-1 ? ....... y-1 y ....
↕ ↕
.............. j-2 j-1 j答案就是: 看 next[ next[j-1] ] 的值。 回顾一下过程:
- 求取
next[j]的值 - 先拿到
next[j-1] = y - 然后比较发现
str[y]不等于str[j-1] - 于是不看
y位置了, 而是看next[y]位置, 即比较str[ next[y] ]和str[j-1]
为什么可以这样做呢? 不要急, 一步一步来。
先看看 next[y] 的含义, 他表示字符串 str 的位置y 左侧的子串 0......y-1 上的 "最大相同真前后缀的长度"。 若 next[y] = k 则说明真前缀 0.....k-1 和真后缀 ......y-1 相同。 如下:
字符串可以画成这样:
0............. k-1
↕ ↕
.............. y-1 y .................j-2 j-1 j
└───────────────────────┘
也可以画成这样:
┌──────────────────┐
0............. k-1 .............. y-1 y
↕ ↕ ≠ 此时已经知道 str[y] 不等于 str[j-1], 但 str[y-1] 还是等于 str[j-2] 的
..................................j-2 j-1 j因为我们是抽象讲解的, 所以可能不容易看明白, 下面我在用其他图案画一下, 目的是为了让大家发现这个时候字符串 str 的特殊子串。 此时的字符串 str, 可以确定有两部分相同真前后缀,
- 一个是
0.....y-1和.....j-2是相同的, 这是因为next[j-1] = y - 一个是
0.....k-1和.....y-1是相同的, 这是因为next[y] = k
现在我们用特殊形状表示四段特别的区域
0 🔺🔺🔺🔺🔺🔺 🔶🔶🔶🔶🔶🔶 y-1 y 🍕🍕🍕🍕🍕🍕 ✨✨✨✨✨✨ j-2 j-1 j
↑
这里面有位置 k-1, k首先, 由于 0.....y-1 和 .....j-2 是相同的, 所以 🔺 区域和 🍕 区域是相同的, 🔶 区域和 ✨ 区域实现相同的, 至于单个区域内部是什么, 我们不在乎, 因为他们不影响结果。 此时, 字符串将变成下面这样
0 🔺🔺🔺🔺🔺🔺 🔶🔶🔶🔶🔶🔶 y-1 y 🔺🔺🔺🔺🔺🔺 🔶🔶🔶🔶🔶🔶 j-2 j-1 j
↑
这里面有位置 k-1, k折叠一下, 比较容易看观察:
0 🔺🔺🔺🔺🔺🔺 k-1 ... 🔶🔶🔶🔶🔶🔶 y-1 y
↕ ↕ ↕ ↕ ↕ ≠
🔺🔺🔺🔺🔺🔺🔺 ....... 🔶🔶🔶🔶🔶🔶 j-2 j-1 j 中间的 ... 表示他们只是和 k-1 ... 这段的字符相同, 然后就没有什么特殊的了。 画出来只是为了严谨记住： 0.....y-1 和 .....j-1 是相同的。
现在再来一个条件: 0.....k-1 和 .....y-1 相同, 所以 🔺区域 和 🔶区域也是相同的:
0 🔺🔺🔺🔺🔺🔺 k-1 ... 🔺🔺🔺🔺🔺🔺 y-1 y
↕ ↕ ↕ ↕ ↕ ≠
🔺🔺🔺🔺🔺🔺🔺 ....... 🔺🔺🔺🔺🔺🔺 j-2 j-1 j也就是说, 现在有四段被分开的 🔺🔺🔺🔺🔺🔺 都是相同的, 我们分别标记为 1️⃣ 2️⃣ 3️⃣ 4️⃣:
┌────────────────────────┐
0 🔺🔺🔺1️⃣🔺🔺 k-1 ... 🔺🔺🔺2️⃣🔺🔺🔺 y-1 y
↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ↕ ≠
🔺🔺🔺3️⃣🔺🔺🔺 ....... 🔺🔺🔺4️⃣🔺🔺🔺 j-2 j-1 j再重新说一遍: 由于 str[y-1] 和 str[j-2] 是相同的, 并且 str[k-1] 和 str[y-1] 也是相同的, 所以 str[k-1] 和 str[j-2] 是相同的, 故我们得出, 🔺1️⃣🔺 和 🔺4️⃣🔺 是相同的:
错位一下更容易看出玄机
┌───────────────────────────────┐
0 🔺🔺1️⃣🔺🔺🔺 k-1 k ... 🔺🔺🔺2️⃣🔺🔺🔺 y-1 y
↕ ↕ ?
🔺🔺🔺3️⃣🔺🔺🔺 ....... 🔺🔺🔺4️⃣🔺🔺🔺 j-2 j-1 j现在, 明白了为什么可以直接跳到 k 位置比较 str[k] 和 str[j-1] 了吧。 只要 str[k] 和 str[j-1] 相同, 那么就可以得到 next[j] = k。 什么? 你问我如果又不相同要怎么办? 那就继续跳, 下一次比较的就是 str[ next[k] ] 和 str[j-1]。 原理是一样的。
好了, 现在明白为什么可以这样后, 还需要证明它。
证明: 为什么可以跳过某些位置
先回顾一下过程：
- 求
next[j] - 先看
next[j-1] = y, 但str[y]不等于str[j-1]
┌─────────────────┐
0 ....... k-1 k ......... y-1 y .......
↕ ≠
.............. j-2 j-1 j- 再看
next[ next[y] ] = k, 判断str[k]是否等于str[j-1]
┌─────────────────┐
0 ....... k-1 k ......... y-1 y .......
↕ ?
.............j-2 j-1 j为什么可以直接从 y 位置跳到了 k 位置? 换句话说, 你要如何保证 k 和 y 之间, 不存在某个位置 a, 能够使得 真前缀 0.....a 和 真后缀 .....j-1 相同呢?
首先, 你已经理解了为什么只需比较 str[k] 和 str[j-1], 就能够得出 0.....k 和 .....j-1 相等的结论:
┌─────────────────────────────┐
0 🔺🔺🔺🔺🔺 k-1 k ...... 🔺🔺🔺🔺🔺🔺 y-1 y
↕ ↕ ?
🔺🔺🔺🔺🔺🔺 ....... 🔺🔺🔺🔺🔺🔺 j-2 j-1 j但是, 这只能说明它是其中一条相同的真前后缀。 我们如何保证没有比它更长的相同真前后缀呢? 换个说明, 我们要如何证明 k 到 y 之间, 没有一个位置 a, 能够满足 0.....a 等于 .....j-1 呢?
好, 那我们就假设存在这么一个位置 a, 并且 a 不等于 k 也不等于 y。
0 ......k...... a ...... y ...
↕ ↕ ↕
..... ............... j-1同样的, 先看看前提和假设:
- 前提
next[y] = k0.....y-1等于.....j-1(这个大家记得这个吧, 由next[j-1] = y推导出来的)
- 假设
- 存在
a满足0.....a等于.....j-1 - 并且
a不是k
- 存在
既然假设 0.....a 和 .....j-1 相等。 好, 那就说明 a 前面的字符, 和 j-1 的前面字符都是相同的:
0 ......k...... a-3 a-2 a-1 a ...... y ...
↕ ↕ ↕ ↕ ↕ ↕
..... ............... j-4 j-3 j-2 j-1同时, 因为 0.....y-1 是等于 .....j-1, 所以 str[a] 等于 str[j-1] 等于 str[y-1]。 故 a 前面的字符, 和 y-1 前面的字符, 也是相同的。
┌────────────────────────────────────────────┐
│ ┌───────────────────────────┼─────────────────┐
│ │ ┌─────────────────────┼─────────────────┼─────┐
│ │ │ ┌───────────────┼─────────────────┼─────┼─────┐
│ │ │ │ ┌─────────┼─────────────────┼─────┼─────┼────┐
0 ......k...... a-3 a-2 a-1 a .... ................ y-3 y-2 y-1 y ...
↕ ↕ ↕ ↕ ↕ ↕
..... ............... j-4 j-3 j-2 j-1也就是说, 存在 0.....a-1 等于 .....y-1。 这意味着什么? 这意味着 next[y] 的真前缀是 0.....a-1, 真后缀是 .....y-1。 也就是说, next[y] 的值可以是 a。 但我们的前提是什么? 是 next[y] = k。 我们的假设是什么? 是 a 不等于 k。 所以出现矛盾了, 假设不成立。 故不存在位置 a, 并且 next[y] != a, 还要满足 0.....a 和 .....j-1
总结求取 next 数组过程
- 求取
next[j] - 先看
next[j-1]是多少, 假如next[j-1] = y - 比较
str[y]是否等于str[j-1]。 (因为我们求的是 j 位置的 next, 所以不管怎么变, 都是要和str[j-1]相比较的)- 若
str[y]等于str[j-1], 则可以直接求出next[j] = y+1。 (为什么不可能大于 y+1 前面已经给出证明) - 若
str[y]不等于str[j-1], 则继续:
- 若
- 查看
next[y]是多少, 假如next[y] = k - 比较
str[k]是否等于str[j-1]。 (为什么不需要看 k-y 之间的值前面也给出了证明) - 重复上面过程, 每次都会往回跳, 直到
- 查看
next[?]是多少, 发现next[?] = 0 - 比较
str[0]是否等于str[j-1]- 如果相等, 说明
next[j-1] = 0+1 - 如果相等, 就直接赋值
next[j-1] = 0 - 结束求取
next[j]的过程。
- 如果相等, 说明
代码
【老师版本, 带注释】:
int[] getNextArray(char[] str) {
// KMP 主流程中算法控制了传入的 str 不可能是 空
if (str.length == 1) {
return new int[] {-1}; // 首元素位置的值是什么其实无所谓
}
int[] next = new int[str.length];
next[0] = -1;
next[1] = 0;
int j = 2; // 要求的 next[j]
int yk = next[j-1]; // 或者直接写成 yk = 0。 yk 就是等待比较的那个字符的位置下标, 即前面讲解中的 y, 然后是 k, ....
while (j < next.length) {
if (str[j-1] == str[yk]) { // 求取 next[j] 时, 始终都是和 str[j-1] 比较, 变化的只会是前面的跳板
// next[j] = yk+1; // 匹配到 0......yk-1 等于 ......j-1, 故 next[j] = yk, 因为长度 = yk-1+1
// j += 1; // 计算出 next[j] 后, 接着计算下一个
// yk = next[j-1]; // 每次计算 next[j] 时, 都会先获取 next[j-1] 的值。
// 上面三行代码, 可以直接简写成下面一行代码
next[j++] = ++yk; // 涉及到证明1
} else if (yk > 0) {
// 直接往前跳, next[yk] 到 yk 部分不用看, 肯定找不到满足的。 涉及到证明 2
yk = next[yk];
} else {
next[j] = 0; // 跳到 0 位置了还不相等, 说明没有相同真前后缀
j += 1; // 继续求下一个元素的 next
// yk 不需要变, 因为 yk 等于 0了, 下一个值的 next 最多也就是 1
}
}
return next;
}【py版本, 已验证】:
def getNextArr(pat):
le = len(pat)
if le == 1:
return [-1]
_next = [0] * le
j = 2
yk = _next[j-1]
while j < le:
if pat[j-1] == pat[yk]:
_next[j] = yk + 1
j += 1
yk = _next[j-1]
elif yk > 0:
yk = _next[yk]
else:
_next[j] = 0
j += 1
return _next证明时间复杂度 O(M)
证明方式和 KMP 的证明方式几乎一模一样, 甚至更简单:
- 创建两个变量,
j和j-yk j的最大值是 M, M 表示str的长度, 也就是 KMP 中的pat长度j-yk最大值也是 M, 因为yk最小值是 0- 查看循环三个分支
- 分支1,
j和yk都加加, 故j变大,j-yk不变 - 分支2,
yk变小, 故j不变,j-yk变大 - 分支3,
j加加, 故j变大,j-yk变大
- 分支1,
- 三个分支, 无论走哪一个,
j和j-yk都会有一个值变大 - 而循环结束条件又只需要
j达到 M - 故极端情况下,
j-yk一直变大, 循环轮次 M 次 - 然后就只能
j变大了, 循环轮次 M 次 - 最多循环 2M 次, 故时间复杂度是 O(M)
🍕 KMP 算法搜索所有匹配的字符串
A A A A A B A A A B A
|
A A A A此时匹配完毕 txt[0] 匹配完毕, 按照暴力搜索的方法, 它会直接重置 pat 指针 j 回到 0, 但实际上 pat 指针可以继续留在这个位置上。 原因是前面的内容我们已经比较过了, 是相等的, 没必要再比较。
这个时候 lps 数组出来了, 如果此时的 j 是 4, lps[4] = 3, 那么利用 j = lps[4] 就可以让 j 下一次继续停留在下标 3 位置上。
lps[i] 等于 子串 pat[0...i] 的最长前缀, 但要求这个前缀不能等于子串的长度。 比如 lps[0] 表示求取长度为 1 的字符串的 lps, 因为不能等于本身, 所以 lps[0] = 0。 而计算 lps[1] 时, 会判断长度为 2 的字符串 lps, 这个时候就需要比较了, 可能是 1,可能是0。 这就是和 next 数组不一样的地方。
- “AAAA”, lps[] is [0, 1, 2, 3]
- “ABCDE”, lps[] is [0, 0, 0, 0, 0]
求解 lps:
利用 len 变量求解, len 是 pat 的下标, 它始终指向子串的前缀最后一个字符。 所以, 过程如下:
- 如果 pat[len] 等于 pat[i], 说明目前的前缀和后缀是匹配的
- len += 1
- lps[i] = len
- i += 1
- 如 pat[len] 不等于 pat[i], 说明目前的前缀和后缀不匹配, len 需要退一个再比较看看
- len -= 1
- 如果 len 退到 0 后, 都还不匹配, 则说明 没有前缀和当前子串的后缀匹配, 故 lps[i] = 0
- 注意, lps[i] 只可能是一个一个递增的。 如果 len 回退到 0 后, 后面的 lps[i] 是不可能突然变大的, 只能是继续慢慢+1+1
KMP 怎么使用 lps
- 首先, pat[j] 和 txt[i] 字符比较
- 如果 ✔️, 则 i 和 j 一起加加
- 当 j 匹配完了, 由于 j++, 所以 j 会等于 pat 的长度。 此时需要更新 j = lps[j-1] (这一点是 next 数组没有的)
- 如果 ❌
- 此时我们知道前面有一些字符是匹配的, 即 pat[...j-1] 和 txt[...i-1] 是匹配的。 因为 j 只会在匹配时才会增加
- 同时我们也知道 lps[j-1] 的值, 表示的是 pat[...j-1] 的最大真前后缀长度
- 通过这两点, 我们可以得出, 我们不需要匹配 txt[i-j, i-1] 这部分内容, 因为这部分内容肯定是匹配的。 (这一点和 next 数组一样)
- 也就是说, 此时可以通过 lps[j-1] 获得下一次匹配的 pat 下标, 而 i 是不需要移动的。 (这一点和 next 数组不太一样)
lps 数组的优势在于查找字符串出现次数时, 可以有效的减少匹配次数, 比如匹配 AAAAA 和 AAA 时。 next 数组, 当找到一个后就结束了。
最开始, i 和 j 都从 0 开始。
A A A A A B A A A B A
0
A A A A
0
✔️, i++, j++
A A A A A B A A A B A
1
A A A A
1
✔️, i++, j++
A A A A A B A A A B A
2
A A A A
2
✔️, i++, j++
A A A A A B A A A B A
3
A A A A
3
✔️, i++, j++
j++ 后发现 j==4 匹配完毕, 不像暴力搜索那样, 它会直接将 j 重置回 0。
通过 lps[j-1], 我们可以得到 j = lps[4-1] = 3, 即 j 还会继续指向下标 3
A A A A A B A A A B A
4
A A A A
3
✔️, i++, j++
j==4, j = lps[4-1] = 3
A A A A A B A A A B A
5
A A A A
3
❌, j = lps[j-1]
此时发现不匹配, 于是 j 根据 lsp[j-1] 重置回 2
A A A A A B A A A B A
5
A A A A
2
❌, j = lps[j-1] = 1
A A A A A B A A A B A
5
A A A A
1
❌, j = lps[j-1] = 0
A A A A A B A A A B A
5
A A A A
0
❌, 因为 j==0, 所以 让 i++
A A A A A B A A A B A
6
A A A A
0
✔️, j++, i++
A A A A A B A A A B A
7
A A A A
1
✔️, j++, i++
A A A A A B A A A B A
8
A A A A
2
✔️, j++, i++
A A A A A B A A A B A
9
A A A A
3
❌, j = lps[j-1]
A A A A A B A A A B A
9
A A A A
2
❌, j = lps[j-1]
A A A A A B A A A B A
9
A A A A
1
❌, j = lps[j-1]
A A A A A B A A A B A
9
A A A A
0
❌, j == 0, 故 i++
A A A A A B A A A B A
10
A A A A
0
END🍕 KMP 算法总结
实际上, next 数组和 lps 数组是一模一样的。 前面 next 数组中的 KMP 算法, 只不过是在找到后就退出了, 想要修改的话, 只需要将循环结束条件中的 M < len(pat) 去掉就可以了。 然后添加一个判断, 如果 M 等于 pat 的长度时, 下一个匹配的元素应该继续维持在 pat 的最后一个元素, 这样就和 lps 数组的实现一样了。
然后就是 next 数组和 lps 数组的求法, 也都是一样的, 变量都是用来保存当前位置的最长前后缀。 至于数组中的值, lps 数组只是比 next 快一格罢了, lps 数组的第一个元素值固定是 0, 而 next 数组的前两个元素值固定是 -1, 0。
- next[j] 求取的子串是 pat[...j-1]
- lps[j] 求取的子串是 pat[...j]
所以本质上 next 和 lps 数组是一样的, 只不过一个包含自己, 一个不包含自己而已。 他们求取的都是最长前后缀, 并且长度不等于字符串本身。
然后就是求取的方法, 两者本质上是一样的。
- next 每次跳的元素数量是不一定相同的, 但它确保每次跳的位置, 都是前缀的最后一个元素。 因为每次都是根据 next[?] 的值进行跳的
- lps 每次跳的元素数量也是根据前面的 lps 求取出来的。 并且也能保证每次跳的位置都是前缀的最后一个元素。 方法也是产品主前面的 lps[?] 的值。
lps 的求取, 相当于 next 求取过程中, 比较的是 pat[j] 而不是 pat[j-1]。 即包不包含元素本身这一个区别罢了。