单模匹配问题与KMP算法

单模匹配

字符串是一个序列，序列的每个下标对应一个字符，单模匹配指在字符串A(目标串)中查找字符串B(模式串)，若A中包含B则返回B首次出现时的首字母下标。朴素算法的流程是首先B对齐A首位，然后逐位比较字符，若某位匹配失败则退出，然后将B对齐A的第二位…重复上述步骤。该算法的代价为\(O(ab)\)。

def bruteFind(target, pattern):
    offset = 0
    while 1:
        if offset+len(pattern) > len(target):
            return -1
        for i in range(len(pattern)):
            if target[i+offset] != pattern[i]:
                offset += 1
                break
        else:
            return offset

def bruteFind(target, pattern):

offset = 0

while 1:

if offset+len(pattern) > len(target):

return -1

for i in range(len(pattern)):

if target[i+offset] != pattern[i]:

offset += 1

break

else:

return offset

KMP算法的匹配步骤

KMP是由Knuth等计算机科学家在1977年发表的著名算法。KMP算法可在\(O(a+b)\)时间完成单模匹配，其中\(a,b\)为目标串与模式串的长度。这里通过把朴素算法逐步优化为KMP算法来介绍。

考虑“模式串首字符在模式串唯一”的特殊情况，若朴素匹配在目标串\(k\)下标失配，根据“首字符唯一”的信息，显然下轮匹配可直接把模式串对齐目标串的\(k\)下标，总匹配代价显然为\(O(a+b)\)。该情况提供了一种思路：能否预先从模式串归纳某些信息，利用这些信息在匹配时进行“长程跳跃”？

首先定义辅助数组\(next[j]\)为“模式串的\([0,1…j]\)子串的最长首尾相同部分的长度（不含该子串自身长度），该数组是KMP中最重要的辅助数组(该定义与原版KMP有些区别)。

然后给出KMP的“长程跳跃”策略，若在目标串\(k\)下标失配，下轮对齐位置取决于\(next[k-1]\)表示的长度，直接把首对齐到尾即可(无首尾相同部分时把模式串首位对齐目标串\(k\)下标)，简单反证：“该策略所跳过的对齐位置中，若某位置可以匹配，则能找到更长首尾相同部分”。此时还可以发现“长程跳跃”后，由于上述子串有首尾相同部分，而这部分已匹配过，下轮可直接从失配位置\(k\)匹配，整体匹配过程目标串完全不回溯。所以若暂不考虑如何求\(next\)及其代价，该策略的代价为\(O(a)\)。

KMP算法的next数组

接下来的问题是如何求出\(next\)，这是KMP算法最复杂的环节，这里计模式串为\(p\)，流程如下：

1）开始循环，其中\(j\)循环的取\(1,2…\)到\(p\)的最大下标，并赋值\(x=next[j-1]\)。

2）若\(p[j]=p[x]\)，则赋值\(next[j]=x+1\)，回步骤(1)。

3）若\(p[j]\neq p[x]\)且\(x-1 \geq 0\)，则赋值\(x=next[x-1]\)，回步骤(2)。

4）若\(p[j]\neq p[x]\)且\(x-1 < 0\)，则赋值\(next[j]=0\)，回步骤(1)。

简单讨论上述求\(next\)步骤的正确性，如图A1A2表示\(next[j-1]\)对应的相等子串，根据数值关系图中\(k = next[j-1]\)，B1B2表示\(next[k-1]\)对应的相等子串，结合与A1A2的关系得出B1=B2=B3…类推可得一系列这类关系。下面证明\(next[j]\)的值只能落在\(L_{A1} + 1, L_{B1}+1, L_{C1}+1…\)中，利用该命题可直接验证上述步骤的正确性：

1) 若\(next[j] > L_{A1}+1\)，则\(L_{A1}=next[j-1]\)可取更大值，导致矛盾。

2) 若\(L_{A1}+1 > next[j] > L_{B1}+1\)，则\(L_{B1}=next[L_{A1}-1]=next[next[j-1]-1]\)可取更大值，导致矛盾。

……

3) 说明\(next[j]\)只能取\(L_{A1} + 1, L_{B1}+1, L_{C1}+1,…\)。

4) 进一步的有\(next[j]\)只能取\(next[j-1]+1,next[next[j-1]-1]+1,…\)。

这里(4)刚好解释了上述求\(next\)数组的各个步骤的正确性。

KMP算法的时间复杂度

KMP中的匹配步骤是无回溯的，所以聚合分析立即得出这一部分的摊还代价。但求\(next\)的步骤中存在不确定次数的回溯（即步骤(3)的子循环），这里用势能函数来求这一部分的摊还代价。

摊还分析是基于“运算序列”的，这里划分运算序列仅含一种运算，即每次循环，于是定义第\(i\)次运算结束后的势能\(\Phi_i=next[i-1]\)，下标始于1。显然其满足势能函数性质\(\Phi_1=0,\Phi\geq 0\)。根据\(next\)数组性质，第\(i\)次外层循环结束后\(\Phi_i – \Phi_{i-1} \leq 1\)。且在第\(i\)次循环中，每执行次(3)子循环，势能必然减少一些。根据该势函数，显然有总摊还代价大于等于总实际代价，所以总的(3)子循环执行次数一定不多于外层循环的执行次数。故求解\(next\)数组步骤的总代价有上界\(O(b)\)。

综上所述KMP算法的代价为\(O(a+b)\)。

KMP算法的具体实现

def kmpFind(target, pattern, next):
 
    pLen = len(pattern)
    tLen = len(target)
    i = offset = 0
 
    while offset + pLen <= tLen and i < pLen:
        if target[i + offset] == pattern[i]:
            i += 1
        elif i == 0:
            offset += 1
        else:
            offset += i - next[i - 1]
            i = next[i - 1]
 
    if offset + pLen > tLen:
        return -1
    return offset

def getNext(pattern):
 
    next = [0 for i in pattern]
    for i in range(len(pattern)):
        j = i - 1
        while j >= 0:
            j = next[j]
            if pattern[i] == pattern[j]:
                next[i] = j+1
                break
            else:
                j -= 1
 
    return next

def main():
    p = 'aab'
    t = 'ababbababaabab'
    nxt = getNext(p)
    i = kmpFind(t,p,nxt)
    print(i)

main()

def kmpFind(target, pattern, next):

pLen = len(pattern)

tLen = len(target)

i = offset = 0

while offset + pLen <= tLen and i < pLen:

if target[i + offset] == pattern[i]:

i += 1

elif i == 0:

offset += 1

else:

offset += i - next[i - 1]

i = next[i - 1]

if offset + pLen > tLen:

return -1

return offset

def getNext(pattern):

next = [0 for i in pattern]

for i in range(len(pattern)):

j = i - 1

while j >= 0:

j = next[j]

if pattern[i] == pattern[j]:

next[i] = j+1

break

else:

j -= 1

return next

def main():

p = 'aab'

t = 'ababbababaabab'

nxt = getNext(p)

i = kmpFind(t,p,nxt)

print(i)

main()

发表评论 取消回复

发表评论取消回复