KMP
简单写一个KMP算法:
def Transform_Table(pattern):state = len(pattern)table = [[0 for _ in range(256)] for _ in range(state)]X = 0table[0][ord(pattern[0])] = 1for i in range(1, len(pattern)):current_char = ord(pattern[i])for j in range(256):if j == current_char:table[i][j] = i + 1else:table[i][j] = table[X][j]X = table[X][current_char]return tabledef search(str_data,table):final_state = len(table)result = []state = 0for i in range(len(str_data)):state = table[state][ord(str_data[i])]if state == final_state:result.append(i - final_state + 1)state = 0return resultpattern = "ababc"
table = Transform_Table(pattern)str_data = "ababababc"print(search(str_data,table))