KMP字符串匹配算法
今天刚学KMP,做点输出,一方面查找漏洞,加深理解,另一方面帮助大家学习。
应用场合
给你两个字符串 $n$, $m$,问你在$n$是否包含 $m$
例如 $n=”abcabdabcabc”, m=”abcabc”$
朴素解法思想
朴素解法:将m与n逐个对比
从头对比
1
2
3n| a b c a b d a b c a b c
m| a b c a b c
^(指针)对比到下面这一步时发现不同
1 | n| a b c a b d a b c a b c |
- 朴素解法:将m串往后退一格,继续逐一对比下面是朴素解法后面的其中几步
1
2
3n| a b c a b d a b c a b c
m| a b c a b c
^(指针)1
2
3n| a b c a b d a b c a b c
m| a b c a b c
^(指针)可以计算出,朴素算法的时间复杂度是$O(nm)$1
2
3n| a b c a b d a b c a b c
m| a b c a b c
^(指针)
KMP算法思想
然而,在朴素解法第3步中,我们其实可以直接将$m$串往后移动3个位置而不是1个位置
依据:在前面比对完的的$abcab$串中,前缀ab和后缀ab相同,也即该串的最大公共前缀后缀长度为2,因此我们可以直接跳过中间的$b、c$,也即将$m$串往后移动2个位置。
- 上接朴素匹配的第二步
1
2
3n| a b c a b d a b c a b c
m| a b c a b c
* * ^(指针)
这时,我们仍然可以保证,$m$串前面的$ab$与$n$串后面的$ab$(上面*标记的两个位置)依旧可以对应,于是可以使指针不回退,继续向前搜素。正因为KMP算法中的指针并没有回退,而是一直向前或暂时暂停,因此具有$O(n+m)$的优秀时间复杂度
了解了KMP算法的原理之后,要做的就是计算$m$串每个位置前缀字符串的最大前缀后缀公共长度,例如:
1 | a b c a b c |
next数组预处理
如果能够预处理出上面的数据,那么我们匹配时,就可以最大程度的往后移,节省时间。当然,这个预处理也是KMP算法的核心(也最难理解)。
这个预处理数组在算法书中被记作$next$数组,$next[i]$表示$m$串前$i$个字符的最大公共长度,例如对应例子中的$m$串,$next[1]=next[2]=next[3]=0,next[4]=1,next[5]=2,next[6]=3$。
假设现在已经得到$next[j]$了,怎么递推$next[j+1]$呢?
分两种情况递推:
1.$m[j+1]=m[next[j]]$
看上去很复杂,我们来看具体例子
1 | m| a b c a b c |
假设我们已经求出$next[5]=2$,(显然,可以直接看出这个结果,为什么前面可以求得$next[5]=2$不重要,重要的是怎么用前者递推后者),当$m[j+1]=m[next[j]]$时,也就是$m[5]=m[2]$,这时候最大公共长度也就是在前面的基础上+1,$next[6]=next[5]+1$。应该不难理解。
很巧妙的一点是,$next[5]=2$表示的是前5个字符的最大公共长度是2,这时候的$m[next[5]]$恰巧又是最大前缀的后面那个字符。因此要比对$j+1$位置和上一次最大前缀后一个字符是否相同,就是条件中的$m[j+1]=m[next[j]]$
看代码:
1 | void getnxt() |
2.当然就是$m[j+1]\ne m[next[j]]$
这是核心(难点)中的核心(难点)
为了方便说明,我们以字符串”abaaba#abaabaa”为例
1 | a b a a b a # a b a a b a a |
假设我们现在已经求得$k=next[13]=6$,要递推得到$next[14]$
上面的代码已经给出结论,我们需要不断的回溯$k=next[k]$直到遇到$-1$或者匹配成功。
为什么是$k=next[k]$呢?
看上面的例子中,虽然 # 和$a$不相同,但是我们已经知道$a$前面的$next[13]$个字符和整个字符串最前面的$next[13]$个字符是相同的(也就是$5$和$6$部分)。在上面的例子中,又有$k=next[k]=next[next[13]]=next[6]=3$,这时候就有,前$6$个字符的最大前缀后缀公共长度为$3$,也就是$1=2$,又有$5=6$,所以得到$1=4$(匹配成功)所以要只需从$1$和$4$的后面继续对比即可。当然也可能遇到$-1$,也就是回溯到$next[0]=-1$也不能匹配,那么下一个位置的最大公共长度自然就是$0$了
最终代码
1 | /* |