KMP算法,又称看毛片算法,是用来检索某个字符串是否属于另外一个的算法
把被检索的字符串称为主串
检索的字符串称为子串
一个直觉上的算法如下：
例子#1
主串 | S | a | b | a | b | c | a | b | c | a | c | b | a | b | |
子串 | T | a | b | c | a | c |
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
第一列都是a 通过
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
第二列也都是b 通过
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
第三列不同了 跳出
后移一位
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
从第二列开始比较,开始便不同,跳出
再后移一位
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
从第三列开始比较,比较到第七列,b和c不同,跳出
再后移一位
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
从第四列开始比较,开始便不同,跳出
再后移一位
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
从第五列开始比较,开始便不同,跳出
再后移一位
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
从第六列开始比较,到最后都匹配,完成
这样我们大概需要(主串长度 x 字串长度)次比较完成
例子#2
主串 | S | a | b | c | d | e | W | g | h | i | . | . | . | ... |
子串 | T | a | b | c | d | e | f |
我们发现到了字串的第六个字母f开始和主串不匹配了,那么我们最多可以把子串后移多少位呢? 匹配的部分a b c d e各不相同, 所以a肯定不和b c d e匹配,那么我们可以把a移动到他们后移,即最多移动5位,把a移动到原先f的位置上
(这里注意我们比较了f和w,他们是不同的,但是没有比较a和W,所以我们尚未知道a和W是否不同)
a | b | c | d | e | W | g | h | i | . | . | . | . | . | . | . | ... |
a | b | c | d | e | f |
例子#3
主串 | S | a | b | c | d | a | W | g | h | i | . | . | . | . | . | . | . | ... |
子串 | T | a | b | c | d | a | f |
依然是从f开始不匹配的,那么我们可以把子串后移的多少位呢
因为无法判断主串中与第二个a匹配对应的位置开始往后的部分是否与整个子串相匹配,所以子串最多向后移动4位,即a移动到第二个a的位置上,然后再进行判断.
主串 | S | a | b | c | d | a | W | g | h | i | . | . | . | . | . | . | . | ... |
子串 | T | a | b | c | d | a | f |
那么回到例子#1,运用这样的方法我们可以这样比较：
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
第二趟
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
第三趟
a | b | a | b | c | a | b | c | a | c | b | a | b |
a | b | c | a | c |
我们这里利用了一些新的附加信息
1.当从 子串第三个字符(第一个c)开始不匹配的时候,后移两位
2.当从 子串第五个字符(第二个c)开始不匹配的时候,后移三位
我们发现,如果我们预先有这样的一些信息,我们可以减少运算步骤
可以减少运算的信息：当第?个字符开始不匹配的时候,我们最大后移是?位
观察例子#2和例子#3,再将子串中匹配部分按照最大后移的位数后移后,我们得到：
2#原先的 | a | b | c | d | e | |||||
2#后移的 | a | b | c | d | e |
3#原先的 | a | b | c | d | a | ||||
3#后移的 | a | b | c | d | e |
我们发现我们是将匹配部分一位一位的后移,知道出现和原先的尾部某个连续部分相同为止,如果一直没有,后移匹配部分的长度便停止
例子#4
计算下面子串的匹配部分的最大后移
a b a b a
我们使用一种记录方式: (后移位数,和尾部匹配的字符数), 显然的如果没有匹配,“和尾部匹配的字符数”是0,如果匹配,“和尾部匹配的字符数” = 字符串长 - 后移位数
a | b | a | b | a | ||||||
a | b | a | b | a | (1,0) | |||||
a | b | a | b | a | (2,3) | |||||
a | b | a | b | a | (3,0) | |||||
a | b | a | b | a | (4,1) | |||||
a | b | a | b | a | (5,0) |
我们发现,对于有匹配的情况,其最大的“和尾部匹配的字符数”所对应的“后移位数”就是最大后移位数,原因很简单,“和尾部匹配的字符数”越大,就代表我们不需要比较的部分越大,显然对于固定长度的子串而言需之后要比较的部分就越小,这正是我们需要的.
注意这里最大后移位并不是取后移位的最大值,比如(4,1)这个组合,虽然移动的更向后,但是取它却是错误的,这里有一个反例：
例子#5
主串 | S | a | b | a | b | a | b | a | X | X | O | O |
子串 | T | a | b | a | b | a | X |
此外,“尾部匹配的字符数”是相对后移位数的不减函数,因为它除了为0的情况外,必然虽然后移位数增加而减少,所以上述的计算实际上我们只需要进行到(2,3)便可以停止了,即是当我们第一次遇到匹配的情况的时候循环便结束了.
如果全部“尾部匹配的字符数”全部为0,即使像例子#2中的子串,则 最大后移位数 = 字符串长
我们来建立一个列表来存储“当第?个字符开始不匹配的时候,我们最大后移是?位”这样的有用的信息
例子#6
子串 | a | b | a | b | a | a | b | a | b |
列表 | 1 | 1 | 2 | 2 | 2 | 2 | 5 | 5 | 5 |
KMP算法
这...其实,前面的只是一些热身而已～～～
在思想上KMP算法与上面讲的完全一致,都是要让子串向后移动尽可能远的一段距离来达到提高效率的目的,但在具体操作上KMP算法与上面的方法又有所不同.
KMP算法为子串引入了一个参数next[j]
next[j] = max{k | 0 < k < j 且 'p[0]...p[k-1]' = 'p[j-k+1]...p[j-1]'}
j是开始出现不匹配的字符的位置,next[j](使p[0]...p[k-1] = p[j-k+1]...p[j-1]成立的k的最大值)就是上文提到的是最大“和尾部匹配的字符数”,那么我们如何求得next[j]呢？
由例子#6发现
next[0] = -1 (开始便不相同,只能后移一位,为了满足a的前面的字符串长度0减去next[0]等于1,必须取next[0]=-1)
next[1] = 0 (对于第一个字符相同,第二个字符不同的情况,其匹配部分只有一个字符,只能后移一位,两者相减是0)
目前有的数据 next=[-1,0,
把第一行的最后一个字符标号记为i, 与之对应的第二行的字符标号记为j
从第三个字符不匹配开始,有(i,j)=(1,0)
0 | 1 | |
a | b | |
0 | 1 | |
a | b |
b<>a (i,j)=(1,0) 第二行后移一位
0 | 1 | ||
a | b | ||
0 | 1 | ||
a | b |
注意此时的i=1对应的j=-1, (i,j)=(1,-1),将i和j分别加1,(i,j)=(2,0),此时的j即是next[2],next=[-1,0,0
计算出next[2]之后,把第三个字符加上,计算从第四个字符不匹配开始的情况next[3], 依然是比较第一行的最后一个和第二行对应的
0 | 1 | 2 | ||
a | b | a | ||
0 | 1 | 2 | ||
a | b | a |
注意此时a=a, (i,j)=(2,0),将i和j分别加1,(i,j)=(3,1),此时的j即是next[3],next=[-1,0,0,1
以此类推,如果出现i,j标号的字符相同或者j=-1的情况,便把i和j分别加1,此时的j即是next的新值
0 | 1 | 2 | 3 | ||
a | b | a | b | ||
0 | 1 | 2 | 3 | ||
a | b | b | b |
(i,j)=(3,1) 分别加1 (i,j)=(4,2) next[4]=2,next=[-1,0,0,1,2
0 | 1 | 2 | 3 | 4 | ||
a | b | a | b | a | ||
0 | 1 | 2 | 3 | 4 | ||
a | b | a | b | a |
(i,j)=(4,2) 分别加1 (i,j)=(5,3) next[5]=3,next=[-1,0,0,1,2,3
0 | 1 | 2 | 3 | 4 | 5 | ||
a | b | a | b | a | a | ||
0 | 1 | 2 | 3 | 4 | 5 | ||
a | b | a | b | a | a |
(i,j)=(5,3) 这里我们发现a<>b,显然我们需要把第二行后移,后移的位数可以这样计算
第二行的第三位开始不匹配,我们又要进行了一次从第三位开始不匹配的计算(下面的后两行),结果是我们已经知道的next[j]=1(j=3)
0 | 1 | 2 | 3 | 4 | 5 | ||||
a | b | a | b | a | a | ||||
0 | 1 | 2 | 3 | 4 | 5 | ||||
a | b | a | b | a | a | ||||
0 | 1 | 2 | 3 | 4 | 5 | ||||
a | b | a | b | a | a |
新的j=1
0 | 1 | 2 | 3 | 4 | 5 | ||||
a | b | a | b | a | a | ||||
0 | 1 | 2 | 3 | 4 | 5 | ||||
a | b | a | b | a | a |
a<>b,继续,我们要又进行一次从第一位开始不同的比较,新的j等于next[j](j=1),j=0
0 | 1 | 2 | 3 | 4 | 5 | |||||
a | b | a | b | a | a | |||||
0 | 1 | 2 | 3 | 4 | 5 | |||||
a | b | a | b | a | a |
此时a=a, (i,j)=(5,0),将i和j分别加1,(i,j)=(6,1),此时的j即是next[6],next=[-1,0,0,1,2,3,1
0 | 1 | 2 | 3 | 4 | 5 | 6 | |||||
a | b | a | b | a | a | b | |||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | |||||
a | b | a | b | a | a | b |
(i,j)=(6,1) 分别加1 (i,j)=(7,2) next[7]=2,next=[-1, 0, 0, 1, 2, 3, 1, 2
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |||||
a | b | a | b | a | a | b | a | |||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |||||
a | b | a | b | a | a | b | a |
(i,j)=(7,2) 分别加1 (i,j)=(8,3) next[8]=3,next=[-1, 0, 0, 1, 2, 3, 1, 2, 3
最终的next=[-1, 0, 0, 1, 2, 3, 1, 2, 3]