python之KMP详解
KMP具体是什么我们这里就不做介绍了，我们先从生活中的例子来一步一步进行讲解
先我们有S=“BBCABCDABABCDABCDABDE”
P=“ABCDABD”
我们现在要做的事就是去匹配S和P，算算P在S的那个位置
实际结果就是 S=“BBCABCDABABCDABCDABDE”
P=“________________ABCDABDE”
OK,我们把P右移了13位，也就是M=S[13:13+len(P)] = P
我们先从本质来看看我们究竟要干什么，M=P了，则我们知道位移i=13，len（P）=8，
那么：
S[i+0] = P[0]
S[i+1] = P[1]
S[i+2] = P[2]
S[i+3] = P[3]
S[i+4] = P[4]
S[i+5] = P[5]
S[i+6] = P[6]
S[i+7] = P[7]
也就是说，我们只需要求出P的长度以及位移i的值，我们就知道P究竟在哪里和S的某一段子字符串相匹配了。
我们先来个初级求解
# 求模式串P在T中的起始位置
# version:1.0
T = "abacaabacabacabaabb"*1000
P = "abacab"
for t_key, t in enumerate (T):
if T[t_key:(t_key+len (P))] == P:
print(t_key)
输出为5,9。意思就是在T里面有2个子串和P匹配。求解思路就是先T[0]和P[0]比，通过了，就继续第二个字符比，依次类推。
全部通过了及T[t_key:(t_key+len (P))] == P，我们就算找到了他的起始位置了。
如果其中一项不匹配呢？我们就继续迭代T，这样就是每次都把T，P轮流迭代，一发现不对头，我们就又去把T的下标前进一位继续迭代，你是不是觉得这样的方式非常的麻烦。
我们继续从初级思想出发，我们从上题来看，我们T[0]开始，第一次匹配6个长度的字符串失败了对不，我们就去T[1]去找，但T[1]明显不是a开头的啊，我们可否直接跳过？
OK，那我们现在就给我们的P打上下标吧
P[0]="a"
P[1]="b"
p[2]="a"
p[3]="c"
P[4]="a"
P[5]="b"
为了检测效果，我们就把T串扩大50000呗吧，先来看看1.0版本的执行时间
#coding:utf-8
import time
# 求模式串P在T中的起始位置
T = "abacaabacabacabaabb" * 50000
P = "abacab"
begin = time. time()
result = []
j=0
m=0
_id = len(T)
while 1:
if _id<len(P):
break
for i in range(len(P)):
if P[i]==T[i]:
m+=1
if m==len(P):
result.append(j)
j+=1
T = T[1:]
_id-=1
m=0
break
else:
j+=1
T = T[1:]
_id-=1
m=0
break
#print(result)
print(time.time()-begin)
耗时：17.317999839782715秒
下面接着我们的1.1版本了
#coding:utf-8
import time
# 求模式串P在T中的起始位置
#此时我们遇到P[1]直接就跳过去
T = "abacaabacabacabaabb" * 50000
P = "abacab"
begin = time.time ()
result = []
j = 0
m = 0
_id = len (T)
while 1:
if _id <len (P):
break
for i in range (len (P)):
if P[i] == T[i]:
m += 1
if i == 0 and P[i + 1] != T[i + 1] and T[i+1]!=T[i]:
j += 2
T = T[2:]
_id -= 2
m = 0
break
if m == len (P):
result.append (j)
j += 1
T = T[1:]
_id -= 1
m = 0
break
else:
j += 1
T = T[1:]
_id -= 1
m = 0
break
# print (result)
print (time.time () - begin)
耗时：14.82200002670288秒
还不错，比之前优化了很多了，但此时我们只是要求第一次匹配成功，第二次一旦不一样我们就立马把T右移2位。
这只是一个基础思想，现在我们要做的就是寻找其中的规律了。
我们继续来观察一下P的各个元素吧
P[0]="a"
P[1]="b"
p[2]="a"
p[3]="c"
P[4]="a"
P[5]="b"
我们假设模式串是P[0:2]，ok,我们现在发现只要第二个匹配不符合且第二个元素不等于第一个元素，我们就可以直接右移2位，等于的情况下我们就右移1位。
（a,b），前缀可以是a,,后缀是b,无交集，当第二位是b的时候，我们可以右移2位，当第二位是a的时候，我们就要右移1位。
也就是 如下图：
我们假设模式串是P[0:3]，ok,前面的规则依然是符合的，我们现在只是新加了P[3]进来。
(a,b,a)，前缀可以是a,ab,后缀可以是ba,a,交集为a，当第三位是a的时候，我们右移为0，当第三位是非a的时候，我们就要右移3位。结果如图:
我们再假设模式串是P[0:4],ok,前面的规则依然是符合的，我们现在只是新加了P[4]进来。
(a,b,a,c)，前缀可以是a,ab，aba,后缀可以是bac,ac,a,交集为a，当第四位是c的时候，我们可以右移4位，当第四位是b的时候，我们就要右移2位。结果如图:
好了，我们不继续举例了。
从图中我们可以知道，只要我们的模式串的前缀和后缀有交集，那么我们的右移位数最小就等于已匹配的位数-前后缀的交集数。
为什么这么说呢？
我们设想一下，前面我们已经匹配了，是匹配的什么，匹配的前缀，我们来看原模式串，P(abacab)的所有的前缀:
a,ab,aba,abac,abaca。我们去匹配，不就是第一个前缀匹配成功，再去匹配第二个前缀，再第三，第四....一直持续到全部匹配吗？这些匹配信息我们就可以拿来利用了。那我们如果第一个成功，第二个没成功怎么办？我们难道就暴力破解，直接右移一次？好的，那我们假设第二次匹配就是ad呢，我们明明知道d不可能等于a，我们为什么不干脆直接右移2位呢？这不就少了一次for循环的计算过程了吗？
我们继续举例，这次来一个大家都玩过的游戏，火车接力扑克游戏，你一张，我一张，遇到一样的就把前面对应的全部吃掉。。
你不会没玩过吧？那你的童年可真的太可怜了，哈哈哈哈哈。我们还是贴个图说明一下吧，7和7一样，那么你就可以把7到7的所有扑克牌都拿走了。如图
这里利用了什么信息呢，前面有个7了，我去匹配，一直到我的牌出现另一个7再算匹配成功。
也就是类似a（xxxxxxxxxx...xxxxxxxx）a，也就是我下一次不匹配，我就右移一位，还不匹配，我又右移一位，一直到匹配为止。
只不过我们这里不停的变化了我们的a，里面有无数的a嵌套在里面而已。也就是我们的P在不停的变化。这里的前后缀的交集永远为1。
aba（x）不是吗？我前面有个a的前缀了，我的后缀出现了另一个a，那我是不是下次就可以直接右移2次了，反正中间的b是不可能在下一次for循环的第一次迭代成功的嘛！所以我右移位数=已匹配位数-已匹配字符串的前后缀交集数
我们现在转过来看这就是一个next函数，也就是f（x）=x-set（x）
我们先把set（x）算出来，让它变成一个常量。
def intersection(P):
offset_table = {} # 位移对照表
for length in range (len (P)):
new_P = P[:length + 1]
prefix = set () # 前缀
suffix = set () # 后缀
if len (new_P) < 2:
offset_table.update ({length: 0})
else:
for j in range (1, len (new_P)):
prefix.add (new_P[:len (new_P) - j])
suffix.add (new_P[j:])
offset = prefix & suffix
index = len (offset)
offset_table.update ({length: index})
return offset_table
OK，现在我们来升级我们的代码为1.2版本看看效果
import time
# 求模式串P在T中的起始位置
# 此时我们遇到P[1]直接就跳过去
def intersection(P):
offset_table = {} # 位移对照表
for length in range (len (P)):
new_P = P[:length + 1]
prefix = set () # 前缀
suffix = set () # 后缀
if len (new_P) < 2:
offset_table.update ({length: 0})
else:
for j in range (1, len (new_P)):
prefix.add (new_P[:len (new_P) - j])
suffix.add (new_P[j:])
offset = prefix & suffix
index = len (offset)
offset_table.update ({length: index})
return offset_table
T = "abacaabacabacabaabb" * 50000
P = "abacab"
offset_table = intersection (P)
begin = time.time ()
result = []
j = 0
m = 0
_id = len (T)
while 1:
if _id < len (P):
break
for i in range (len (P)):
offset = i - offset_table.get (i)
if T[i] != P[i]:
if i == 0:
T = T[1:]
j += 1
_id -= 1
m = 0
break
T = T[offset:]
j += offset
_id -= offset
m=0
break
else:
m += 1
if m == len (P):
m = 0
result.append (j)
_id -= offset
j += offset
T = T[offset:]
break
print (time.time () - begin)
耗时：5.890999794006348秒
OK，我们的效率大大提升了，我们现在可以把代码再优化一下了
作者：胡桓
