以前在学校的时候上数据结构就听老师讲解过这个算法，当时估计在赶着下节课需要交的作业所以压根就没听，之后也没去看它的原理，前几天看到一篇博客讲述的就是这个算法，感觉非常的浅显易懂，所以就照着写了个简易的程序。原文地址

关于KMP算法的概念上面的链接说的非常清楚，强烈建议想了解这个算法的人都去看看。

#

简单来说，这个算法也是基于遍历的比较的，只是普通的遍历没有利用起来之前比较过的信息，而KMP算法是把之前比较的信息保存了起来。反正我对于这个算法的第一映像就是要匹配的字符串是需要按某种方法移动的。这种移动的次数肯定是比穷举法的移动次数少的多。

代码

def KMP(s,m):
        """
       (s,m)->int
       return the index if s contains the m
       return -1 if not find the sub string m
       warning:if there are many sub strings,return the first
       """
        index=0

        sindex=0

        length = len(s)-len(m)+1

        for i in range(length):

            sindex=index

            mindex=0

            k=-1

            while s[sindex]==m[mindex]:

                if k==-1 or s[index+k]==m[mindex]:

                    k+=1

                if mindex==len(m)-1:

                    return index

                sindex+=1

                mindex+=1

            index+=(1 if k==-1 or k==0 else mindex-k)

        return -1

s为字符串，m为需要匹配的字符串，由于我们要保存之前比较的信息，那么这里再定义了一个变量作为记录使用k，k的值也就是所谓的部分匹配值，让它初始值为-1。定义好了保存信息的变量，下面就开始比较，当接受比较的两个字符相等时就判断k，若满足代码中的条件则执行k+=1。这个步骤是什么意思呢，因为我们要保存比较过的已经确认是相等的字符的个数，我们字符串的移动中会使用到这个数值。使用的地方就是在我们一直比较到对应的字符不相等的时候。

当我们发现有字符不匹配的时候，那么我们按照普通的遍历，肯定是一拍脑门，让匹配字符串也就是m后撤一步从头再进行一个字符一个字符的比较。退一步海阔天空哦，但是要是这样子撤退的话，那我们之前所作的比较岂不是浪费了？在这个讲究和谐的时代，这么明目张胆的浪费实在是可耻行为，为了保持不可耻的作风并且为节能做出贡献，那么我们现在就要利用之前比较过的信息，也就是轮到k该上场是时候了。代码中index+=(1 if k==-1 or k==0 else mindex-k)这行就是k的主战场，它计算了m这个字符串需要向后移动多少位，而不是闭着眼睛就是往后移一位(当然了，经过计算还是向后移动一位的话，那就自觉的移动一位吧，我相信m小姐在这个时候会原谅我们的)。那我们这么计算移动位数的根据是什么，移动的少了那就失去了意义，移动的多了不用说更加不可以了，根据就是计算k的地方,也就是下面的代码所描述的地方：

if k==-1 or s[index+k]==m[mindex]:
                    k+=1

假设有两个字符串s=ABCASDG和m=ABCD,当我们比较到m[3]的时候，这时s[3]==A,m[3]==D,发现不相等了，根据k的记录，已经比较过的子字符串中没有出现重复的字符(这里的重复是指m中的)，这里AB互不相等，那么根据这个信息我们知道要是移动一位的话那开头的字符就必须是不相等的，这里A =\= B，所以要是移动一位的话也是白移的，那么移动两位呢，同样的方式，A =\= C，所以移动两位也是徒劳，由于我们在比较到m[3]的时候之前已经确认相等的字符只有两个，并且这两个都不相等，那么只好在移动一位了，由于这位我们还没有保存，所以就它了，这里我们就移动三位。所以保存比较过的信息可以让我们迅速的知道接下去要向后移动几位才合适。

#

这次也总算是基本了解了这个算法的实现原理，也了却了心里的一个节点。