KMP

KMP

• 불일치가 발생한 텍스트 스트링의 앞부분에 어떤 문자가 있는지를 미리 일고 있으므로, 불일치가 발생한 앞부분에 대하여 다시 비교하지 않고 매칭을 수행
• 패턴에 중복이 있을 경우에만 적용 가능
• 패턴을 전처리하여 배열 next[M]을 구해서 잘못된 시작을 최소화함
• 시간복잡도: O(M+N)
• 텍스트에서 abcdabc까지는 매치되고 e에서 실패한 상황 패턴의 맨 앞의 abc와 실패직전의 abc는 동일함을 이용

# T : target / P : pattern

def pre_process(P):

    M = len(P)
    lps = [0] * len(P)
    
    j = 0

    for i in range(1,M):
        if P[i] == P[j]:
            lps[i] = j + 1
            j += 1
        else:
            j = 0
            if P[i] == P[j]:
                lps[i] = j + 1
                j += 1  

    return lps


def KMP(T, P, lps):

    N = len(T)
    M = len(P)

    i, j = 0, 0
    pos = -1
    while i < N:
        if P[j] == T[i]:
            i += 1
            j += 1
        else:
            if j!= 0:
                j = lps[j-1]
            else:
                i += 1
        if j == M:
            pos = i - j
            break

    return pos

T = 'abcdabeeababcdabcef'
P = 'abcdabcef'


N = len(T)
M = len(P)
lps = pre_process(P)
print(lps)

pos = KMP(T, P, lps)
print(pos)