标签：相等 parent 实现 findding next 算法 str KMP ind
# coding=utf-8
def get_next_list(findding_str):
# 求一个字符串序列每个位置的最长相等前、后缀
j = 0 # 最长相等前缀的末位
next = [0] # next 数组用于保存字符串每个位置的最长相等前、后缀的长度值
# i 是最长相等后缀的末位
for i in range(1, len(findding_str)):
while j > 0 and findding_str[i] != findding_str[j]:
# 如果当前 前缀末位（j）字符与当前i位置的字符不相等时，j回退 PS：j的值也表示findding_str[：i+1]最长相等前、后缀的长度值
j = next[j-1]
if findding_str[i] == findding_str[j]:
j += 1
next.append(j)
return next
def KMP(findding_str, next, parent_str):
ind = 0
for i in range(len(parent_str)):
while parent_str[i] != findding_str[ind]:
if ind == 0:
break
# parent_str[i] != findding_str[ind] 且 ind != 0 时，从findding_str[ind] 左侧的字符串的最大相等前缀处开始比较
ind = next[ind-1]
if parent_str[i] == findding_str[ind]:
ind += 1
if ind == len(findding_str):
print(i, ind, parent_str[i - ind + 1: i+1])
ind = 0
# break
if __name__ == '__main__':
parent_str = 'aabafgggahaabaafaabaahatjhrtjabaafaabaahaabaafaabaahaabaaf'
findding_str = 'aabaaf'
KMP(findding_str, get_next_list(findding_str), parent_str)
标签：相等,
parent,
实现,
findding,
next,
算法,
str,
KMP,
ind
From： https://www.cnblogs.com/teanon/p/16723203.html