[Python知识库]用Python简单写一个KMP

KMP

简单写一个KMP算法：

def Transform_Table(pattern):
    state = len(pattern)
    table = [[0 for _ in range(256)] for _ in range(state)]

    X = 0
    table[0][ord(pattern[0])] = 1

    for i in range(1, len(pattern)):
        current_char = ord(pattern[i])
        for j in range(256):
            if j == current_char:
                table[i][j] = i + 1
            else:
                table[i][j] = table[X][j]

        X = table[X][current_char]
    
    return table

def search(str_data,table):
    final_state = len(table)

    result = []
    state = 0
    for i in range(len(str_data)):
        state = table[state][ord(str_data[i])]
        if state == final_state:
            result.append(i - final_state + 1)
            state = 0
    
    return result

pattern = "ababc"
table = Transform_Table(pattern)

str_data = "ababababc"

print(search(str_data,table))