MENU

KMP(1)

July 1, 2018 • Read: 2757 • 算法阅读设置

字符串匹配问题

首先我们先把问题明确一下,给定两个字符串P[1..P.len]和S[1..S.len],找出P在S中第一次出现的位置L,即最小的L满足P[1..len]=S[L..L+len-1]。例如”HA”在”WAHAHA”中第一次出现的位置是3(这一节约定下标都是从1开始)

暴力算法

从小到大枚举L,然后判断P[1..len]=S[L..L+len-1]的条件是不是满足;不满足就+1试下一个L。伪代码如下:

Match(P,S)
    For L = 1...S.len - P.len + 1
        Found = True
        For i = 1...P.len
            If P[i] ! = S[L + i - 1]
                Found = False
                Break
            If Found
                Return L
    Return -1

用一张图来展示暴力匹配的过程:

上图中第一行的字符串是S,第二行的字符串是P。同时第2行也是枚举L=1时的匹配过程,前5个字符abbba都匹配上了;但是第6个字符失配了。第3~5行是枚举L=2, 3, 4时的匹配过程,都是第一个字符就失配了;第6行是L=5时的匹配过程,第一个字符a匹配上了,第二个字符失配了

KMP算法

首先我们定义一个函数:失配位置f(x)。f(x)=k表示当L=x时,失配的字符是S[k]。注意这个位置是在字符串S上的,而不是P上的。在上面的例子中,f(1)=6, f(2)=2, f(3)=3, f(4)=4, f(5)=6

KMP算法的优化思路就是,枚举L的过程中,跳过使失配位置减少的L。例如我L=1的时候已经辛辛苦苦匹配上5个字符S[1..5]了,在第6个字符失配,也就是f(1)=6。那么失配之后能不能至少从L=5开始匹配,跳过L=2..4。因为L=2..4时,f(2)f(3)f(4)都比f(1)还小。好歹f(5)等于f(1),所以从L=5开始匹配

跳过使失配位置减少的L还有一个好处,就是从L=x跳到L=y时,其实并不用从S[y]开始匹配,而是直接从S[f(x)]开始匹配即可

image

在上图的例子中,L=1时,在f(1)=7失配。这时我们跳到L=4继续(为什么在L=4继续,看上面一段文字),注意继续时我们并不用再比较P[1]和S[4],P[2]和S[5], P[3]和S[6],而是直接比较P[4]和S[f(1)](S[f(1)] = S[7])

image

如上图所示,如果L=x时,P[1..100]与S[x..x+99]匹配上。那么L=x+1时,P[1..99]能与S[x+1, x+99]匹配上当且仅当P[1]=P[2]=P[3]=P[4]=…=P[100],也就是P[1..100]是aaaa….a这样类型的

同理,L=x+2时,P[1..98]能与S[x+2 … x+99]匹配当且仅当P[1]=P[3]=P[5]…=P[99]且P[2]=P[4]=P[6]=…P[100],也就是P[1..100]是ababab…ababab这样类型的。再同理,L=x+3时,P能匹配到S[x+99]的位置当且仅当P[1..100]是abcabcabc…abcabc这样类型的

用更一般的话说,如果在L=x时,P[1..K]匹配上了S[x..x+K-1];那么当L=x+d时,P和S匹配的两段是P[1..K-d]匹配S[x+d .. x+K-1],而S[x+d .. x+K-1]又等于P[1+d..K](根据L=x时的匹配)。所以在P[K+1]失配时,KMP的思路是,找一个最小的d满足P[1..K-d]=P[1+d..K]

形象的说也就是找到P[1..K]的一个最长前缀,并且这个前缀同时也是P[1..K]的一个后缀,也就是P[1..K]的前j个字符组成的字符串和后j个字符组成的字符串相等

比如P[1..6]=”aaaaaa”,那么这个(同时也是后缀的)最长前缀是P[1..5]=”aaaaa”;如果P[1..6]=”abaaba”,那么这个(同时也是后缀的)最长前缀是P[1..3]=”aba”;如果P[1..6]=”ababab”,那么这个(同时也是后缀的)最长前缀是P[1..4]=”abab”……

如果我们知道P[1..K]的(同时也是后缀的)最长前缀是P[1..j],我们就记作next[K]=j。这个next数组也叫作next函数。对于一个字符串P来说,我们可以先手算出对应next数组,例如”bababb”的next=[0, 0, 1, 2, 3, 1]

有了next数组,就意味着我们可以达成KMP的优化思路:

  1. 当匹配P[1..K]与S[x..x+k-1]都成功,而P[K+1]与S[x+K]失配时
  2. 通过将P[next[K]]对准S[x+k-1],实现跳过使失配位置减少的L
  3. 继续比较P[next[K]+1]与S[x+K],而不用从P[1]开始比较

有了next数组,KMP匹配的伪代码是这样的。注意我们特别让next[0]=-1:

j = 0
For i = 1...S.len
{
    //这时p[j]与S[i-1]是匹配上的,尝试匹配P[j+1]与S[i]
    while(j >= 0 && S[i] != P[j + 1])
        j = next[j]
    j = j + 1
    if(j == P.len)
        return i - P.len + 1
}

用图示来展示KMP的过程(已知next数组):
image

上图从第三行开始匹配,注意是P[j+1]匹配S[i],所以一开始S[1..5]匹配上P[1..5]。这时i=6,j=5开始尝试匹配S[6]和P[6],匹配失败,j = next[j]=next[5]=3

于是第4行尝试匹配S[6]和P[j+1]=P[4],成功。之后一直成功匹配到S[7]和P[5]。这时S[8]和P[6]匹配失败,j = next[j]=next[5]=3

于是第5行尝试匹配S[8]和P[4],失败。j = next[j]=next[3]=1。于是第6行尝试匹配S[8]和P[2],失败。j = next[j]=next[1]=0。于是第7行尝试匹配S[8]和P[1],失败。j = next[j]=next[0]=-1。这时j=-1会跳出while循环,j++使得j=0。然后进行下一次i=9的循环

于是第8行i=9, j = 0,尝试匹配S[9]和P[1],成功。之后一直成功匹配到S[13]和P[5]。这时S[14和S[6]匹配失败,j = next[j]=next[5]=3

于是第9行,S[14]匹配P[4]成功,S[15]匹配P[5]成功,S[16]匹配P[6]失败,j = next[j]=next[5]=3。于是第10行,S[16]匹配P[4]成功,S[17]匹配P[5]成功,S[18]匹配P[6]成功,这时找到了一个完成的匹配

假设已知next数组,KMP算法的复杂度显然就是O(i变化的总量+j变化的总量),其中i是从1~S.len,显然一共变换O(S.len)次。J会通过j=j+1变大,也会通过j=next[j]变小。不过j变大的次数与i循环次数一样都是O(S.len)次,而每次j变小最小变到-1。所以j减小的总量最多是S.len+1,也是O(S.len)

Last Modified: November 9, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment