Python|实现KMP算法字符串匹配
问题描述
在解决字符串匹配问题中，若不使用python内置函数，大部分时候会想到使用BF(暴力循环)算法来解决。然而，这样会产生一个问题：算法的时间复杂度过高，匹配的字符串过长，往往会导致计算结果超时。如果使用KMP算法就能减少不必要的循环匹配计算，极大的减少算法的时间复杂度。
解决方案
BF算法与KMP算法
BF算法主要是暴力循环匹配，即模式串的字符一个一个的去循环匹配。
实例：
目标串：ababcabcacbab
模式串(需要在目标串中匹配的字符串)：abcac
a | b | a | b | c | a | b | c | a | c | b | a | b |
|---|
a | b | c | a | c |
|---|
第一次匹配
a | b | c | a | c |
|---|
第二次匹配
a | b | c | a | c |
|---|
第三次匹配
……
如果存在不匹配的情况，就会从目标串的下一个字符继续循环模式串进行匹配，直到匹配成功，或者匹配失败。
KMP算法则巧妙的避免了不必要的循环匹配；首先计算出模式串每个匹配字符的下标，即数组next，然后再进行匹配。
计算next：
a | b | c | a | c |
|---|
由模式串字符依次计算下标：
该位置字符的前缀与后缀相等的最长的前后缀的长度为该位置的next下标。
a:因为a是第一位，所以a的下标为-1；
b:因为b是第二位，所以b的下标为0；
c:因为c的前缀与后缀没有相同的字符串，故c的下标为0；
a:因为a的前缀与后缀没有相同的字符串，故a的下标为0；
c:因为当c的前缀为a时，后缀也能为a，且最长，故c的的下标为1。
所以得：
a | b | c | a | c | |
|---|---|---|---|---|---|
Next | -1 | 0 | 0 | 0 | 1 |
根据下标进行匹配：
a | b | a | b | c | a | b | c | a | c | b | a | b |
|---|
a | b | c | a | c |
|---|
第一次匹配：找到模式串的c与目标串的a不同，观察c的相应下标为0对应模式串位置a，故到a的位置进行下一次匹配；
a | b | c | a | c |
|---|
第二次匹配：找到模式串的c与目标串的b不同，观察c的相应下标为1对应模式串位置为b，故到b的位置进行下一次匹配；
a | b | c | a | c |
|---|
第三次匹配：即匹配成功。
代码实现
class Text:
def __init__(self):
self.dic={}#定义一个字典，来存储并计算字符下标next
self.next=[]#将得到的下标放入next中
def A(self,s):# s为模式串
for i in range(len(s)):
if i not in self.dic:# 将每个模式串的字符下标储存在字典中，初始值为0
self.dic[i] = 0
if i>=2:
for j in range(1,i):# 循环
if s[:i][:j]==s[:i][-j:]: # 找到最长的相同前后缀
self.dic[i]=len(s[:i][:j]) # 记录相应点最长的相同前后缀
if i==0: # 第一个点的下标一定为-1
self.dic[i]=-1
for ke in self.dic: #遍历字典将得到的下标放入next中
self.next.append(self.dic[ke])
def B(self,gl,s):# gl代表目标串，s代表模式串
for i in range(len(gl)): #遍历gl的字符串下标值
for j in range(len(s)): #遍历s的字符串下标值
if len(gl[i:])<len(s): #当gl从i位置取到最后的长度小于s的长度，返回False匹配失败
return False
if gl[i]!=s[0]: #如果目标串的值不等于模式串的第一个值，那么就进行下一个目标串的循环
break
if j==len(s)-1 and gl[i+j]==s[j]:#当满足最后一个模式串与目标串对应位置相等时返回匹配成功
return True
if gl[i+j]!=s[j]:#如果该位置不等
if self.B(gl[i+j:],s[self.next[j]:]):#递归判断，gl返回不相等的位置即gl[i+j],s则返回next所对应的下标s的位置。如果得到True，结束递归，反之得到False
return True
else:
return False
def C(self,gl,s):
if self.B(gl,s):
print('True')
else:
print('False')
f=Text()
gl='ababcabcacbab'
s='abcac'
f.A(s)
f.C(gl,s)
#输出：
#True结语
本文主要介绍了KMP算法的应用及其特点，在算法时间复杂度上的优点，以及与BF算法的不同，并演示如何用python代码来实现KMP算法来解决字符串匹配问题。
END
主 编 | 王文星
责 编 | 王卓越
where2go 团队