KMP

김동완·2022년 4월 14일
0
post-thumbnail

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)
profile
내가 공부한 내용들이 누군가에게 도움이 될지 몰라서 쓰는 벨로그

0개의 댓글