KMP算法(无回溯字符串匹配)基于python实现

时间:2023-01-06 23:58:28

1.问题导出

给你两个字符串,一个是目标串,比如是“ababcabccacbab”,另一个是模式串,比如是“abcac”,现在想在目标串中找出是否含有模式串的子串,如果有,返回第一个字母的下标,如果无,返回-1

当运用朴素的串匹配算法去解答该题时,分为以下两步:

(1)目标串与模式串从左到右依次匹配

(2)当发现不匹配时,转去考虑考虑目标串里的下一个位置是否与模式串匹配

思路非常简单,但是当考虑复杂度时,可以发现,在在坏的情况下,比如:

目标串:“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab”

模式串:“aaaab”

在这里,时间复杂度达到了O(n*m),n为目标串长度,m为模式串长度。在朴素的匹配算法下,由于认为字符串前后是完全独立,所以每次匹配时,都是从头开始匹配,所以效率很低。但是,大部分的字符串都是相关联的。例如在上述的模式串“abcac”中,

 KMP算法(无回溯字符串匹配)基于python实现

按照朴素串匹配算法,当左图中的最后一个字符不匹配时,下一步,是目标串重新开始用另一个字符与模式串做匹配。但是完全可以如下图所示直接跳到更远的地方,拿开始的a与目标串中的a直接做匹配。

KMP算法(无回溯字符串匹配)基于python实现

这便是KMP算法的由来。

2. KMP算法

先考虑朴素的串匹配算法和KMP匹配的过程:

KMP算法(无回溯字符串匹配)基于python实现

上图左边是朴素串匹配算法的一系列情况。状态0的匹配进行到模式串中字符c时失败,此前有两次成功匹配,从中可知目标串前两个字符与模式串前两个字符相同,由于模式串的前两个字符不同,与b匹配的目标串字符不可能与a匹配,所有状态1一定匹配失败。朴素匹配算法未利用这种信息,做了无用功。在看状态2,这里前4个字符都匹配,最后匹配c失败。由于模式串中第一个a与其后的两个字符bc不同,用a去匹配目标串里的b、c也一定失败。跳过这两个位置不会丢掉匹配点,另一方面,模式串中下标为3的字符也是a,它在状态2匹配成功,首字符a不必重做这一匹配。朴素的匹配算法中没有考虑这一问题,总是从头一步步比较。

    在大部分情况下,目标串未知,而模式串是已知的,而且通常在匹配中反复使用,如果先对模式串做一些分析,记录得到的有用信息,就有可能避免一些不必要的信息,提高匹配效率。这种做法是实际匹配前对模式串进行一系列的静态预处理,只需要做一次。KMP算法的精髓就是开发了一套分析和记录模式串信息的机制,而后借助得到的信息加速匹配。

3. KMP运算过程分析   

KMP算法会在预处理的时候,形成一个数组,对应于每个模式串里面的字符,会算出一个值,如下进行分析。 

KMP算法的大概过程由上右图所示,具体的分析过程如下:

首先,第一步,设置两个指向变量i、j,分别指向目标串与模式串的匹配位置,一开始指向目标串与模式串的第一个位置0:

KMP算法(无回溯字符串匹配)基于python实现

当检测到i、j所对应的值匹配时,到第(1)步,i、j分别加1,指向第二个值,直到第(2)步,i、j所对应的值不匹配。当检测到值不匹配时,KMP会调用预处理中数组对应的位于位置2字符c的值,该值在这里为0,说明下一次匹配的时候模式串应该从字符第0个位置开始。这就到了第(3)(4)步,在第(4)步中,又遇到i、j所指向的值不相等的情况,这时调用位置4中字符c的值,该值在这里为1,说明模式串从第1个字符开始,前面的字符0一定是匹配的,最后直到第(5)(6)步,匹配出目标串中的模式串位置。在目标串之中i指向的位置永远不会后退,这就是无回溯的来源。

4.pnext表的构造

KMP算法(无回溯字符串匹配)基于python实现

如上图所示,移动之前最后一个字符为c,可以看到,当按照pnext(预处理表)表移动以后,j所对应位置之前的字符一定能与目标串中的字符对应。这是因为,模式串上的第4个字符之前的a能与模式串前缀(也就是第0位置上的a)中的a相同,程序在检测最后一个c之前已经检测到第3位置与目标串中的相应字符相对应,故当模式串后移时,前缀中的a一定能与目标串中相应位置的字符相匹配。所以pnext表实际上记录的就是最长相等前后缀的长度。以另一个模式串“abcabdabc”为例:第0、1、2、3个字符都没有相同的前后缀,故为0,为方便算法计算,第0个字符设为-1。

KMP算法(无回溯字符串匹配)基于python实现

但从第4个开始,第4个字符为1,第5个字符为2,。

故综上,“abcabdabe”的pnext表为[-1, 0, 0, 0, 1, 2, 0, 1, 2]。

如果满足条件的位置不止一处,例如“abcabcabc”中的第8个字符c,那么只能做最短的移动,将模式串移到最近的那个满足上述条件的位置,以保证不遗漏的可能。

5.  复杂度及总结

    一次KMP算法的完整执行包括构造pnext表和实际匹配,设模式串个目标串长度分别为m和n,KMP算法的时间复杂性是O(m+n)。由于在多数情况下m<<n,因此可以认为这个算法复杂度为O(n),显然优于朴素撇批算法的O(m+n)。而且许多场景需要用一个模式串反复在一个或多个目标里匹配。例如在文本里查找和替换某个字符串就是典型例子。在这种情况下,构造模式串的pnext表的工作只需要做一次,后面匹配中只需简单的反复使用。

附:

pnext表构造(基于python实现):

def gen_pnext(p):
    """生成pnext表,用于KMP算法 """
    i, k, m = 0, -1, len(p)
    pnext = [-1] * m #初始元素全设为-1
    while i < m-1: #生成下一个pnext值
        if k == -1 or p[i] == p[k]:
            k,i = k+1, i+1
            pnext[i] = k
        else:
            k = pnext[k] #退到跟短相同前缀
    return pnext

串匹配(KMP算法):

def matching_KMP(t, p, pnext):
    """KMP串匹配,主函数"""
    j, i = 0, 0
    n, m = len(t), len(p)
    while j < n and i < m:
        if i == -1 or t[j] == p[i]:
            j, i = j+1, i+1
        else:
            i = pnext[i]
        if i == m:
            return j-i
    return -1