KMP 문자열 검색 알고리즘

파이썬 코드로 작성한 KMP 알고리즘이다.

이해하기 어렵다면 아래 사이트를 참고하자.

https://bowbowbow.tistory.com/6

def getPi(pattern):
    m, j = len(pattern), 0
    pi = [0] * m
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j-1]
        if pattern[i] == pattern[j]:
            j += 1
            pi[i] = j
    return pi


def kmp(string, pattern):
    ret = []
    pi = getPi(pattern)
    n, m, j = len(string), len(pattern), 0
    for i in range(n):
        while j > 0 and string[i] != pattern[j]:
            j = pi[j-1]
        if string[i] == pattern[j]:
            if j == m - 1:
                ret.append(i-m+1)
                j = pi[j]
            else:
                j += 1
    return ret