KMP算法(超详细!!!)
in 算法 with 0 comment

KMP算法(超详细!!!)

in 算法 with 0 comment

0x01 介绍

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特莫里斯普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

0x02 朴素算法

朴素字符串匹配的思路非常简单,就是我们每个人都可以想到的暴力解法。我们需要在s1中找到不否包含s2,那么可以遍历s1的每个字符位置,然后向后匹配s2字符串长度的字符。例如:

s1: a c a a b c
s2: a a b 
      ↑

我们发现此时的ca不匹配,那么说明从s1的第0个位置无法匹配,那么我们继续下一位。

s1: a c a a b c
s2:   a a b 

依次类推,这种做法的时间复杂度就是O((len(s1)-len(s2)+1)*len(s2)),显然不够优秀。

0x03 KMP算法

观察下面的例子:

s1: b a c b a b a b a a b c b a b
s2:         a b a b a c a
                      ↑

我们发现此时bc已经不匹配了,此时如果按照朴素算法的思路,应该从s1的下一位开始从头匹配。

s1: b a c b a b a b a a b c b a b
s2:           a b a b a c a
              ↑

但是我们发现向右挪动一位显然也匹配不成功。

s1: b a c b a b a b a a b c b a b
s2:             a b a b a c a
                      ↑

如果挪动两位的话,可以发现s2中有部分字符和s1的前缀字符串是匹配的。那不还是没有匹配成功吗?前后有什么区别呢?对于一个非常长的s1和一个非常长的s2的进行匹配的话,你显然会相信如果两个字符串前面有较多字符匹配(一眼能看到的所有字符),那么两个字符串能够匹配的几率会很大;如果一开始就不匹配的话,显然就不用看后面的了。

好,现在我们的问题就是如何在出现不匹配的时候,快速跳到下一个前缀匹配较多的位置(针对每个s1开始的位置)?观察s2前后的位置变化

s1: b a c b a b a b a | a b c b a b
s2:         a b a b a | c a
s2':            a b a | b a c a                       

不难发现(其实很难发现QAQ)s2[:i]的后缀和s2'的前缀匹配,并且此时匹配了3个字符,而此时的i是在s2的第5个位置,那么需要向右挪动的距离就是5-3=2。非常好理解,我们知道s2[:i]s1[:i]的后缀是匹配的,而s2[:i]的后缀和s2'的前缀匹配,那么s2'的前缀必然和s1[:i]的后缀匹配,而匹配多少正是我们需要的。

0x0301 next数组的计算

我们可以定义函数$f(i)$表示s2[:i]后缀和s2'前缀的最大匹配长度(注意:长度小于i),可以计算出上面例子中的所有$f(i)$的值:

      1 2 3 4 5 6 7
s2:   a b a b a c a
f(i): 0 0 1 2 3 0 1

我们需要注意边界情况$f(1)=0$。首先可以想到暴力版的$f(i)$求解思路,先枚举所有位置,再枚举所有长度。

f = [0] * (len(s2) + 1)
for i in range(1, len(s2) + 1):
    for j in range(i):
        if s2[i - j:i] == s2[:j+1]:
            f[i] = j

但是这种做法显然不够优秀。怎么优化?首先观察一下。

f(5):    a b a b a | c a
             a b a | b a c a

当我们计算f(5)的时候发现此时最大匹配长度是3,接着我们需要计算f(6)

f(6):    a b a b a c | a
             a b a b | a c a
                   ↑

此时cb显然不匹配,那么此时跳到哪是最好的呢?最左边a的位置重新匹配是最好的选择吗(暴力解法)?显然不是,我们知道f(3)=1

f(3):    a b a | b a c a
             a | b a b a c a

那么我们此时应该回退到f(3)的位置继续比较,因为这么做我们就可以充分利用前缀和后缀相同的信息,这样前缀和后缀重叠部分不用再参与比较。如果此时后一位字符相同的话,我们的最大匹配长度就是f(3)+1

f(6):    a b a b a c | a
                 a b | a b a c a

但是我们发现此时cb不同,我们需要继续回退,此时就要会退到f(1)的位置。

f = [0] * (len(s2) + 1)
f[0], i, j = -1, 0, -1
while i < len(s2):
    while j != -1 and s2[j] != s2[i]:
        j = f[j] # 回退的过程
    i += 1
    j += 1
    f[i] = j

上面这个过程我觉得解释的还是不够清楚,以后继续补充~。

0x0302 尾声

好,接着就是回到问题的最开始

s1: b a c b a b a b a | a b c b a b
s2:         a b a b a | c a
s2':            a b a | b a c a  

此时我们已经知道了怎么从s2s2',现在要做的就是利用上面所计算的$f(i)$函数值来求解s1中是不是包含s2的问题。代码思路非常简单了,从s1s2的开头枚举,如果此时s1[i]!=s2[j],那么此时我们可以通过$f$函数确定j的下一个位置就是$f(j)$。

需要考虑的边界条件就是当j>=len(s2)的时候,说明我们在s1中找到了s2,那么就匹配成功了。

n, m = len(s1), len(s2)
i = j = res = 0
while i < n:
    while -1 != j and s1[i] != s2[j]:
        j = f[j]
    i += 1
    j += 1
    if j >= m:
        res += 1
        j = f[j]
return res

可以发现这个代码和前面计算$f(i)$的代码有很多相似性。

reference:

https://baike.baidu.com/item/kmp%E7%AE%97%E6%B3%95/10951804?fr=aladdin

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses