字符串模式匹配之KMP算法

概述

字符串匹配算法有BF算法，和KMP算法。BF算法原理简单，但耗费性能，事间复杂度为O(mn)。而KMP算法原理相对复杂，但效率很高，时间复杂度为O(m+n)。

其中m,n代表被匹配字符串和匹配字符串的长度

KMP算法原理

将匹配字符串求出一个next数组，每一个匹配字符对应next数组中一个值。在匹配时，遇到不匹配的字符，查出对应的next值，决定从匹配字符串的对应位置继续进行匹配。

代码实现（python）

    def get_next(T,next):  
        #计算匹配字符串内各个字符对应的值，并放入next数组中  
        i,j=0,-1  
        next[0]=-1  
        while i<len(T):  
            if j==-1 or T[i]==T[j]:  
                i+=1  
                j+=1  
                if i<len(T):  
                    next[i]=j  
            else:  
                j=next[j]  


    def kmp(S,T):  
        length=len(T)  
        next=[0]*length  

        get_next(T,next)#获取next  
        print("next为:",next)  

        i,j=0,0  
        while i<len(S) and j<len(T):  
            if j==0 or S[i]==T[j]:  
                i+=1  
                j+=1  
            else:  
                j=next[j]  
        if j>=len(T):  
            print("匹配成功，匹配到的位置为：",i-j)  
            return i-j  
        else:  
            print("匹配失败")  
            return 0  


    kmp("abcabaabacabcd","abcd")