kmp 알고리즘(문자열 매칭)

잘 설명된 문서: https://1ambda.github.io/91/algorithm/algorithm-part2-4/

시간복잡도는 하나하나 검사할경우 O(N*M)이지만 KMP는 O(N+M)이란다.

방법론.

1. next배열을 만든다. 아래는 패턴 10100111에 대한 next배열을 만드는거다.

사진에 대해서 설명하면.

0) next배열을 구하기 위해서 위쪽과 아래쪽에 같은 문자열을 둔다. 아래쪽은 한칸 오른쪽인 상태로 시작한다.

2) 불일치가 발생하면 아래쪽의 비교문자열을 불일치 이후에 첫글자가 첫번째로 일치하는 곳으로 이동시켜준다. 

또 j==4일때 불일치가 발생했는데 불일치가 발생한 곳부터 1을 검색해보면 바로 뒤에 1이 있으므로 거기로 위치를 옮겨준다. 이런식으로 계속 한다.

불일치가 발생하지 않으면, 아래 비교문자열을 옮기지 말고 다음 숫자를 비교한다.

next리스트를 만드는 파이썬 소스코드이다.

# -*- encoding: cp949 -*-
next = [0 for i in xrange(50)]
def initnext(p):
    next[0] = -1
    i = 0; j = -1
    while i<len(p):
        next[i] = j#next[i] = next[j] if (p[i]==p[j] and j>=0) else j
        while((j>=0) and (p[i]!=p[j])):
            j = next[j]
        i += 1; j += 1
 
def main():
    p = '10100111'
    initnext(p)
    print next[1:len(p)]
 
if __name__=='__main__':
    main()

2. 이것을 개선할수 있다. 위의 10100111의 유한 상태 장치를 만들어 보면

이다. 이 그림을 설명하자면 위쪽에서 next배열은 [ 0 0 1 2 0 1 1 ] 이다. 이건 10100111의 두번째 인덱스부터 대응된다.(첫번째 1은 -1이다.) 

next배열의 첫번째 0의 의미는 10100111의 두번째 인덱스인 0이 10100111의 첫번째 인덱스로 향한다는것을 뜻한다. (그래서 위의 그림도 두번째 0에서 첫번째 1로 이어져있음.)

next배열의 두번째 0의 의미는 10100111의 세번째 인덱스인 1이 10100111의 첫번째 인덱스로 향한다는 것이다. (그림보면 세번째 1에서 첫번째 1로 이어져있음.)

나머지도 이와 같다. 근데 이걸 개선시킬수있다고 한다. 개선은 위의 유한상태장치에서 'next배열을 따라서 간 이후의 글자가 똑같을 경우 한칸을 더 이동할 수 있다' 정도로 해석하면 된다.

ex) 세번째 1은 첫번째 1로 향하는데 이건 둘이 같으므로 한칸 더 이동할수 있다.(이경우 맨 앞의 네모로 이어짐.) 또 네번째 0은 두번째 0으로 이어지는데 이것도 같으므로 한칸 더 갈수있다.(이경우 첫번째 1로 가게됨.)

이렇게 개선시킨 유한상태장치를 그려보면 이렇게된다.

그리고 next배열을 다시 만들어본다 가정하면 이렇게 된다. [ 0 -1 0 2 -1 1 1](첫번째는 -1이라 생략) 이걸 소스코드에 적용시키려면 위의 코드의 주석부분에서 주석을 풀고 원래 식을 지우면 된다.

이제 개선된 next배열까지 구했다. 그럼 [ 0 -1 0 2 -1 1 1]로 어떻게 탐색을 할 수 있을까?

맨 위의 긴 문자열은 긴 텍스트고, 아래의 10100111은 찾을 문자열이다. 첫번째에서는 숫자 1에서 불일치가 발생하였다.(빨간네모부분) 불일치가 발생한 위치는 인덱스 3이고(인덱스는 1부터시작한다고 가정), 이건 next배열에서 두번째인 -1이다.(위에서 말했듯이 next배열에서 첫번째는 -1인데 생략했다.) -는 오른쪽 방향이다. -1이므로 오른쪽으로 한칸 간다.

그다음 불일치는 0에서 발생하는데, 0은 인덱스 2번째이고, next배열에서 첫번째인 0이다. 0이면 불일치가 발생한 그 자리를 말하는거이므로 첫번째 문자열을 거기로 옮겨준다. 다음 불일치인 0도 마찬가지이다.

그다음 불일치는 끝에서 두번째인 1인데 이것의 인덱스는 7이다. next배열에서 여섯번째 원소를 찾아보면 1이다.(-1다음의 1.) -가 오른쪽이랬으니 +는 왼쪽으로 가란 소리이다. 불일치가 발생한 위치에서 왼쪽으로 한칸의 위치에 첫번째 글자를 위치시켜준다. 

그다음도 위와 같다. next배열이 1이므로 왼쪽으로 한칸 이동시켜주고 검색해보면 문자를 찾는다.

아래는 kmp소스코드이다.

# -*- encoding: cp949 -*-
next = [0 for i in xrange(50)]
def initnext(p):
    next[0] = -1
    i = 0; j = -1
    while i<len(p):
        next[i] = next[j] if (p[i]==p[j] and j>=0) else j
        while((j>=0) and (p[i]!=p[j])):
            j = next[j]
        i += 1; j += 1

def kmp(p,t):
    initnext(p)
    i = 0; j = 0
    while j<len(p) and i<len(t):
        while((j>=0) and (t[i]!=p[j])):
            j = next[j]
        i += 1; j += 1
    if j==len(p):
        return i-len(p)
    return i

def main():
    text = 'ababababcababababcaabbabababcaab'
    pattern = 'abababca'
    i = 0; pre = 0
    while True:
        pos = kmp(pattern, text[i:])
        pos += pre
        i = pos + len(pattern)
        if i<len(text):
            print '패턴이 발생한 위치 {}'.format(pos)
        else: break
        pre = i
    print '스트링 탐색 종료.'

if __name__=='__main__':
    main()

---

위에껀 학교 알고리즘 책에 나온 kmp고 알고리즘 문제 해결 전략 책에 나온 kmp.

# -*- encoding: cp949 -*-
def getpartialmatch(N):
    m = len(N)
    pi = [0]*m
    begin = 1; matched = 0
    while begin + matched < m:
        if N[begin + matched] == N[matched]:
            matched += 1
            pi[begin+matched-1] = matched
        else:
            if matched == 0:
                begin += 1
            else:
                begin += matched - pi[matched-1]
                matched = pi[matched-1]
    return pi

def kmp(H,N):
    n = len(H); m = len(N)
    ret = []
    pi = getpartialmatch(N)
    begin = 0; matched = 0
    while begin <= n-m:
        if matched < m and H[begin + matched] == N[matched]:
            matched += 1
            if matched == m:
                ret.append(begin)
        else:
            if matched==0:
                begin += 1
            else:
                begin += matched - pi[matched-1]
                matched = pi[matched-1]
    return ret

print kmp('ababbaba','aba')