KMP 字符串匹配算法

main_list = "aaababaaaaababa"  #主串
sub_list = "ababa"  #字串

getnext函数：

用来给出指示：如果当前位置不匹配，要移动字串的位置多少。这里引入了最大前缀和后缀的概念。

def getnext(sub_list):
    length = len(sub_list)
    next_list = [0 for i in range(length)]
    next_list[0] = -1
    j = -1
    i = 0
    
    while i< length-1:
        
        if j == -1 or sub_list[i]==sub_list[j]:
            j+=1
            i+=1
            next_list[i] = j
        else:
            j = next_list[j]
    
    return next_list

KMP函数：

匹配函数，一次匹配，如果当前位置不匹配，根据getnext数组指示移动数组。返回字串头在主串的位置，若字串不存在与主串中则返回-1

def KMP(main_list, sub_list):
    length_main = len(main_list)
    length_sub = len(sub_list)
    
    next_list = getnext(sub_list)
    
    i=j=0 #初始化
    
    while i<length_main and j<length_sub:
        if j==-1 or main_list[i] == sub_list[j]:
            j += 1
            i += 1
        else:
            j = next_list[j]
        
    if j == length_sub:
        return i-j
    else:
        return -1