KMP模式匹配算法

 KMP算法主要解决的问题是如何较为高效地在主串中寻找指定的字串。这种算法可以大大避免朴素匹配中出现的重复遍历的情况。算法的实质是利用字子串自身所具有的一些特殊性质，得到一个函数返回函数Next，从而通过函数Next来避免大量重复遍历的情况。
下面先给出函数Next的定义：
对于字符串T(也可看成是字符列表)
$Next[j]=\begin{cases} -1 &amp; j=0 \\ max\{k|0&lt;k&lt; j\ and\ T[0:k]=T[j-k:j]\} &amp;当此集合不为空时 \\ 0&amp;其他情况\\ \end{cases}$Next[j]=⎩⎪⎨⎪⎧​−1max{k∣0<k<j and T[0:k]=T[j−k:j]}0​j=0当此集合不为空时其他情况​
定义的意义：设主串为$S$S，子串为$T$T，假设比较进行到了$S[i],T[j]$S[i],T[j]处，且$S[i]!=T[j]$S[i]!=T[j]：
 1.当$j=0$j=0时，$Next[j]=-1$Next[j]=−1，此时需要进行的比较为$S[i+1]$S[i+1]与$T[j+1]$T[j+1]；
 2.当$\{k|0&lt;k&lt; j\ and\ T[0:k]=T[j-k:j]\}${k∣0<k<j and T[0:k]=T[j−k:j]}不为空时，
按照$Next$Next定义取$Next[j]=max\{k|0&lt;k&lt; j\ and\ T[0:k]=T[j-k:j]\}$Next[j]=max{k∣0<k<j and T[0:k]=T[j−k:j]}，因为对于$T[0:j]$T[0:j]已经同$S[i-j:i]$S[i−j:i]比较过且相等，又因为$T[0:k]=T[j-k:j]$T[0:k]=T[j−k:j]，这意味着已经得到$S[i-k:i]=T[0:k]$S[i−k:i]=T[0:k]，故需要比较的只有$T[k:]$T[k:]与$S[i:]$S[i:]，故此时$Next$Next的意义是避免了对$T[0:k]$T[0:k]做无谓的比较，让子串与主串的比较直接从子串的第k处开始。
 3.当为其他情况时，直接从头开始比较。

Next代码

def get_Next(T):
    
    j=0
    Next=[-1]
    for j in range(1,len(T)):
        
        K=[k for k in range(2,j+1) if T[0:k-1]==T[j-k+1:j] and k-1>0]
        if K:Next.append(max(K)-1)
        else:Next.append(0)

    return Next

完整代码

# -*- coding: utf-8 -*-
"""
Created on Fri Mar 15 10:14:32 2019

@author: Administrator
"""

def get_Next(T):
    j=0
    Next=[-1]
    for j in range(1,len(T)):
        K=[k for k in range(1,j) if T[0:k]==T[j-k:j] and k>0]
        if K:Next.append(max(K))
        else:Next.append(0)

    return Next

def Index_KMP(S,T,pos=0): 				#S：主串，T：子串，pos：在主串中开始搜寻的位置
    j=0
    i=pos
    Next=get_Next(T)
    while (i<len(S) and j<len(T)):

        if j==-1 or S[i]==T[j]:
        #即在上一次比较中发现子串T中第一个字母便与S[i]不同，或者是S[i]==t[j],则主串和子串的指标i,j均往后移1个位置
            i+=1
            j+=1
        else:
        #即j!=-1且S[i]!=T[j]
            j=Next[j]
    if j==len(T):
    #如果对于T比较完成，则返回主串中对应位置的开头
        return i-len(T)
    else:
        return -1
    
S='dasdfhaskaslsfkjhfweiu'
T='askasls'
Index_KMP(S,T,pos=0)

关于Next函数的改进$Nextval$Nextval

改进的实质：在S[i]!=T[j]时，在计算$Next$Next的值的同时，如果$j$j位字符与它$Next$Next值所指向的$Next[j]$Next[j]位字符相等，则该$j$j位的$Nextval$Nextval就指向$Next[j]$Next[j]位的$Nextval$Nextval值，这是因为$j$j位字符如果通过$Next$Next回到前面的字符位置后，接下来要进行比较的就是$T[Next[j]]$T[Next[j]]与$S[i]$S[i]，而我们已经比较得到$S[i]!=T[j]$S[i]!=T[j]，故若$T[j]=T[Next[j]]$T[j]=T[Next[j]]，则也有$T[Next[j]]！=S[i]$T[Next[j]]！=S[i]，故需要再次通过$Next$Next返回，即返回至$Next[Next[j]]$Next[Next[j]]；如果不相等，则$j$j位的$Nextval$Nextval值就是它自己$i$i位的$Next$Next值。

Nextval代码

def get_Nextval(T):
    j=0
    Nextval=[-1]
    for j in range(1,len(T)):
        K=[k for k in range(1,j) if T[0:k]==T[j-k:j] and k>0]
        if K:
            if T[max(K)]==T[j]:Nextval.append(Nextval[max(K)])
            else:Nextval.append(max(K))
        else:
            if T[j]==T[0]:Nextval.append(-1)
            else:Nextval.append(0)
            
    return Nextval