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
