알고리즘 - KMP법 (문자열 검색)

brute force method는 일치하지 않는 문자를 만나면 다시 패턴의 첫 문자부터 검사를 수행하지만, KMP method는 검사한 결과를 버리지 않고 효율적으로 사용할 수 있는 알고리즘이다.

 

에를 들어 텍스트 'z a b c a b x a c c a d e f'에서 패턴 'abcabd'를 검색할 때 KMP 알고리즘을 사용해보자.

 

A. 먼저 텍스트와 패턴의 첫 문자부터 차례로 검사를 수행한다. 텍스트의 첫 문자 z는 패턴에 포함되지 않는 문자이므로 불일치하다.

B. 패턴을 오른쪽으로 1칸 민다. 패턴의 앞쪽부터 차례로 검사를 수행해 가면 패턴의 마지막 문자 d가 텍스트의 문자 x와 불일치하다.

C. 여기서 텍스트 안의 ab와 패턴 안의 ab가 일치하는 것에 주목한다. 이 부분이 검사를 마친 부분이라면 패턴의 ab 이후인 cabd와 일치하는지만 검사하면 된다. 그래서 패턴을 3칸 밀어서 ab를 나란히 놓고 검사한다. 

 

이처럼 KMP 알고리즘은 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여 패턴의 이동을 되도록이면 크게 하는 알고리즘이다.

그런데 몇 번째 문자부터 검사를 다시 시작할지 패턴을 이동할 때마다 계산한다면 비효율적이다. 그래서 '몇 번째 문자부터 다시 검색할지'값을 표로 만들어서 문제를 해결한다.

 

 

KMP에서 사용하는 표 만들기

표를 작성할 때는 패턴에서 겹치는 문자열을 찾는다. 패턴의 첫 문자가 일치하지 않으면 패턴을 오른쪽으로 1칸 밀어 첫 문자부터 검사해야 하므로 2번째 문자 이후 부분을 생각한다. 또 패턴과 텍스트를 서로 겹치도록 맞추는 것이 아니라 패턴끼리(즉, 패턴과 패턴을) 서로 겹치도록 맞추고 검사를 시작할 곳을 계산한다. 

 

 

이렇게 작성한 표는 건너뛰기 표(skip table)라고 한다.

 

---

 

<code>

def kmp_match(txt, pat):
    pt = 1
    pp = 0
    skip = [0] * (len(pat) + 1) # 건너뛰기 표
    
    #-- 건너뛰기 표 만들기
    skip[pt] = 0
    while pt != len(pat):
        if pat[pt] == pat[pp]:
            pt += 1
            pp += 1
            skip[pt] == pp
        elif pp == 0:
            pt += 1
            skip[pt] = pp
        else:
            pp = skip[pp]
            
    #-- 문자열 검색하기
    pt = pp = 0
    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        elif pp == 0:
            pt += 1
        else:
            pp = skip[pp]
            
    return pt - pp if pp == len(pat) else -1