KMP算法
KMP算法也就是字符串匹配算法, 名字是3个作者的名字首字母. 用来计算匹配串是不是和文本串相匹配
这里以一个例子来看:
eaabcababc // 文本串S
abcabd // 匹配串P
上面的字符串是文本串S, 下面的字符串是匹配串P,此时已经匹配到第三位上, 可以看到最后一个字符a和d不一致, 需要进行下一轮匹配, 那么该让匹配串往后走几位?
直观的来看应该是这样走:
eaabcababc
---abcabd
往后走了3格, 让ab对齐然后继续比较, 这是正确的, 但是回到kmp这个算法, 它是怎么算出3的呢?
kmp引入了next数组, next数组是针对匹配串P的, 而说到这个next数组有以下两点要注意:
-
next数组的计算复杂度为O(m^2), m是匹配串P的长度, 但是可以优化, 最后kmp的复杂度可以达到O(m+n)
-
next数组有不同的版本, 有的版本需要引入 最大公共前缀后缀数组 由它计算next数组, 有的是直接把最大公共前缀后缀数组当作next数组来用.
abcabd
000120 // <- 最大公共前缀后缀数组 (最大也就是最长的意思). 比如, 其中最后一个b对应的next数组的值为2
先解释最大公共前缀后缀数组. 这个数组是动态的从前到后逐个分析子串的最大公共前缀后缀, 即:
// 对匹配串P: abcabd, 其子串有:
a
ab
abc
abca
abcab
abcabd
(注: 这里待分析的子串都是首位字符开头的子串, 不包括中间截取的子串, 比如没有`cab`)
逐个来看:
// next数组[0, 0, 0, 1, 2, 0]的推导过程:
a 的最大公共前缀后缀都是自己, 由于不可以包含自己,所以长度是0.
ab 的前缀是a, 后缀是b, 他们没有公共的,所以长度是0,
abc 同上
abca 的前缀是a, 后缀也是a, 因此最长的公共前后缀是a, 长度是1
abcab 的公共前缀后缀是ab, 长度为2, 因此是2.
abcabd 那个d存在显然是没有公共前后缀了, 因此为0
回到上面的匹配场景:
eaabcababc
abcabd
这时, 前5个字符abcab都是匹配的, 而匹配串P的最后一个d与a不匹配了, d前一个元素b的最大公共前缀后缀数组对应的值为2, 那么, 这个数组就需要往后移动: 已匹配的字符数 - 2 位, 也就是 5 - 2 = 3 位.
暂停一下, 这里要依次说明两点:
1.已匹配的字符数是什么?
2.向后移动3位, 为什么这样移动?
先说已匹配的字符数是什么. 其实就是匹配串P已经匹配成功的字符数(和文本串S的匹配位置无关), 比如上例中abcabd中已经匹配了5个字符, 那么它就是 5.
数值2已经解释了, 映射关系列出来加深理解:
[a, b, c, a, b, d] // <- 匹配串P
[0, 0, 0, 1, 2, 0] // <- 最大公共前后缀数组
再罗嗦一次: 匹配成功一直到b, 当到d的时候不匹配了,因为 d前面的b对应的最大公共前后缀数组的值是2, 所以这里就是2.
再说为什么样移动: 因为公共后缀和前缀一样, 都是两个字符, 也就是ab, 那么我们移动匹配串P的时候就需把前缀和后缀相匹配的部分对齐. 即匹配串移动到最大公共前缀后缀与文本串相等的地方.
对齐的方法就是移动: 已经匹配的长度 - 最大公共前后缀 个位置. 这样表述还是不如例子直观:
已经匹配的长度为5, 最大公共前后缀是2, 那么相减做差就是不公共的长度 3, 也就是向后移动3格就会匹配了.
这里再举两个例子便于理解:
fffabcdaeddd // 文本串S
abcdaf // 匹配串P
[a, b, c, d, a, f] // 匹配串P
[0, 0, 0, 0, 1, 0] // 最大公共前后缀数组
这个例子中, 已经匹配的长度是len(abcda)=5, 最长公共前后缀是1, 那么往后移动4位就可以对齐了, 5 -1 = 4. 再看另一个例子:
fffabaabafff
abaabad
此时, 已经匹配的长度len(abaaba)=6, 最长公共前后缀是(aba)3, 那么往后移动3位就可以对齐, 即 6 - 3 = 3 注意, 这里公共前后缀也可以是a, 但是如果按照len(a)来移动,就会出错, 因为 6 - 1 = 5, 向后移动5位:
反例: 错误的移动5位
fffabaabafff
-----abaabad
预期: 只移动3位
fffabaabafff
---abaabad
虽然文本串S和匹配串P的前缀a是匹配的, 但是此时显然多移动了好几位,错过了可能的匹配成功的部分, 因此也要强调一定是要算最长公共前后缀, 短了就可能匹配不到.
上面的一切都是为了说明这个最长公共前后缀数组的意义. 最长和公共都是必要充分条件, 否则会造成匹配的错误.
下面开始讨论这个next数组的版本, 获取和优化. 还是以最初的那个例子, 直接给出next数组:
[ a, b, c, a, b, d] <- 匹配串P
[ 0, 0, 0, 1, 2, 0] <- 最大公共前后缀数组
[-1, 0, 0, 0, 1, 2] <- next数组
next数组就是把最大公共前缀后缀数组的值往后移了一位, 并给第一个元素补上 -1 他有啥用呢? 其实简单来说就是猫和咪的关系. 回到例子:
eaabcababc
abcabd
此时匹配串P中失配的字符是d, 那么代码中迭代时游标已经走到d这个位置了, 而根据最大公共前后缀数组来计算的话, 就需要往回看一个元素, 也即是b对应的值 2.
那么移动一下以后, 就不需要往回看了, 直接就是d自己的值, 一样是2. 而此时匹配串的游标j, 由于是从0开始计数的, 到第6个元素d的时候其值是5. 那么做差:
j - next[j] = 5 - 2 = 3
和上面的: 已匹配的字符数 - 最后一个匹配字符位 = 5 - 2 = 3 结果是一样的.
其实就是因为不论next数组还是匹配串P的起始index都是0, 所以将最大公共前缀后缀数组的值后移一位生成next数组就使得代码更清爽了.
杠一下, 假设数组index都是从1开始会怎么样? j此时值为6, next数组下标6的值为2, 6 - 2 = 4, 此时,向后移动4位就出问题了. 就算用j - 1也还是很混乱 所以这个版本的next数组完全是因为index起始值为0的特性而生!
接下来看next数组用代码如何生成. 注意, 匹配串P的next数组生成与文本串S毫无任何关系.
TODO 代码实现