[알고리즘 종류] KMP 알고리즘

- KMP 알고리즘

• 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불이리가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행
• 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화함
• * next[M] : 불일치가 발생했을 경우 이동할 다음 위치
• 시간 복잡도 : O(M +N)

출처: https://bbc1246.blogspot.com/2016/08/kmp.html

출처: https://bbc1246.blogspot.com/2016/08/kmp.html

def getPI(pattern):
    pi = [0 for x in range(len(pattern))]
    j = 0
    for i in range(1, len(pattern)):
        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_search(text, pattern):
    pi = getPI(pattern)
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]
        if text[i] == pattern[j]:
            if j == len(pattern) - 1:
                return True
            else:
                j += 1
    return False

: 아직 이건 이해가 잘 가지 않는다...