【专题】KMP
简介
Knuth-Morris-Pratt字符串查找算法,简称为“KMP算法”,常用于在一个文本串S
内查找一个模式串T
的出现位置。这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。时间复杂度O(|S|+|T|)。
朴素算法
给出一个最为常见的朴素字符串模式匹配算法,枚举文本串S
的每一位,作为起点与模式串T
进行匹配。时间复杂度O(|S|*|T|)。
1 | int simple(char* s, char* t, int n, int m) |
朴素算法的运行过程如下:

注意到,如下图,枚举以S[1]为起点,匹配到最后一个字符,S[4]!=T[3],失配之后朴素做法是指针回退,以S[2]为起点开始下一轮匹配,即i=i-j+1, j=0。

毫无疑问,随着文本串S
的长度增加,每一次回退重新匹配会花费大量的时间。那么有没有办法优化呢?
next数组
通过分析模式串T
可以得到next数组
,也可以当作fail数组理解。对于模式串T="abac"
,当匹配到'c'
时失配了,那么说明前面的"aba"
已经匹配成功,"aba"
最长的相等前缀后缀(不包括本身)是'a'
,那么失配'c'
后,我们可以跳过s[3]='a'
(文本串S"aba"
的后缀)与T[0]='a'
(模式串T"aba"
的前缀),直接匹配S[4]='b'
与T[0]='b'
。

为什么是最长的、相等的、不包括本身的前缀后缀呢?看下图自行理解。

由下表可以看出最长相等前缀后缀整体右移,首位加上-1,即是next数组。
模式串 | a | b | a | c |
---|---|---|---|---|
最长相等前缀后缀 | 0 | 0 | 1 | 0 |
next数组 | -1 | 0 | 0 | 1 |
next数组优化
对于失配时S[4]='c'
与T[3]='b'
不相等,由T[1]='b'
与T[3]='b'
相等,得出T[1]='b'
与S[4]='c'
也不相等,我们可以跳过这一步匹配。

注意C++中next
是关键字(迭代器的一个函数),以及字符串下标从0开始和从1开始的代码稍有不同,注意必须求到next[|T|],求字符串匹配数量以及最小循环节都需要用到。下面给出的是字符串下标从0开始的next数组的一种求法:
1 | int nxt[mxn]; |
KMP算法
有了next数组,下面给出KMP算法代码,与朴素算法类似,但是i不用回退了,可以看出求next数组的过程也是一个模式串T
与自身匹配的过程。
1 | int KMP(char* s, char* t, int n, int m) |
KMP算法的运行过程如下:

最小循环节
参考 KMP模板,最小循环节。
定理:
假设S的长度为len,则S存在最小循环节,循环节的长度L为len-next[len],子串为S[0…len-next[len]-1]。 (1)如果len可以被len-next[len]整除,则表明字符串S可以完全由循环节循环组成,循环周期T=len/L。 (2)如果不能,说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L,L=len-next[len]。
index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
char | a | b | c | d | a | b | c | |
next | -1 | 0 | 0 | 0 | 0 | 1 | 2 | 3 |
为方便说明,先设字符串的长度为len,循环子串的长度为L
例1 s0s1s2s3s4s5,next[6]=3 即s0s1s2=s3s4s5 很明显可知:循环子串为s0s1s2,L=len-next[6]=3,且能被len整除。
例2 s0s1s2s3s4s5s6s7,next[8]=6 此时len-next[8]=2,即L=2 由s0s1s2s3s4s5=s2s3s4s5s6s7 可知s0s1=s2s3,s2s3=s4s5,s4s5=s6s7 显然s0s1为循环子串
例3 s0s1s2s3s4s5s6,next[7]=4 此时len-next[7]=3,即L=3 由s0s1s2s3=s3s4s5s6 可知s0s1=s3s4,s2s3=s5s6 从而可知s0s1s2=s3s4s5,s0=s3=s6 即如果再添加3-4%3=2个字母(s1s2),那么得到的字符串就可以由s0s1s2循环3次组成
对于一个字符串,如abcd abcd abcd,由长度为4的字符串abcd重复3次得到,那么必然有原字符串的前八位等于后八位。也就是说,对于某个下标从0开始的字符串S,长度为len,由长度为L的字符串s重复R次得到,当R≥2时必然有S[0…len-L-1]=S[L…len-1]。
那么对于KMP算法来说,就有next[len]=len-L。此时L肯定已经是最小的了(因为next的值是前缀和后缀相等的最大长度,即len-L是最大的,那么在len已经确定的情况下,L是最小的)
模板
1 | char s[mxn], t[mxn]; |