#30 문자열 탐색 - KMP 알고리즘(1)

 문서 편집기나 뷰어 등에서 탐색 기능을 사용하면 문서내의 모든 문자열 속에서 찾으려는 문자열의 갯수와 위치를 보여준다.  전체 문자열의 길이가 N, 찾으려는 문자열의 길이가 M 일때, 단순히 시작위치를 0부터 1씩 옮겨가며 M개의 문자를 비교한다면 시간복잡도는 (N-M+1) * M, 즉 O(NM) 이 된다.   하지만 사실 이보다 더 빠르게 문자열을 탐색할 수 있는 방법이 있다.  이번에는 문자열 속에서 다른 문자열 P의 갯수와 위치를 찾는 KMP 알고리즘을 알아본다.

 

1. KMP 알고리즘의 개요

 KMP 알고리즘의 핵심은 쓸모없는 중간과정을 건너뛰는 것으로 연산의 횟수를 획기적으로 줄이는 것이다.

예를들어 T = 'ABCDABCDABDE' 이고 P = 'ABCDABD일 때, T에 P가 나타나는 횟수와 그 위치들을 찾아보자.

 

먼저 시작 위치를 0 번째 위치로 하고 T와 P를 순차적으로 비교하면 다음과 같은 결과를 얻을 수 있다.

T

A

B

C

D

A

B

C

D

A

B

D

E

P

A

B

C

D

A

B

D

O

O

O

O

O

O

X

 5 번째 문자까지는 일치했지만 6 번째 문자에서 일치하지 않은 것을 확인할 수 있다. 단순한 방법이라면 여기서 탐색 위치를 0으로 옮겨 또다시 M번의 탐색을 해야한다.  하지만 우리는 사실 이 결과에서 6 번째 문자가 일치하지 않았다는 점 보다도 5 번째 문자까지는 일치했다는 점을 활용해야한다

 

 일치한 부분까지의 문자열은 ABCDAB 이다.  여기서 양 끝에서 반복적으로 나타나는 가장 긴 문자열 AB에 주목하자. 이러한 문자열을 문자열의 접두사/접미사(prefix/suffix)라 한다. AB는 문자열 P의 시작부분이며 동시에 T와 일치했던 부분의 끝부분이기도 하다.  이 구간에서 AB가 다시한번 나타나는 4번째 위치 이전까지는 시작위치로 잡고 탐색하더라도 일치할 가능성이 없다.  즉, 다음 탐색의 시작위치를 곧바로 AB가 다시한번 나타나는 구간으로 건너뛸 수 있다는 것이다.  건너뛴 다음의 모습은 다음과 같다.

 

T

A

B

C

D

A

B

C

D

A

B

D

E

P

A

B

C

D

A

B

D

O

O

O

O

O

O

O

물론 여기서도 P[0] 부터 다시 비교할이유는 없다.  우린 이미 AB까지는 일치함을 알고있기 때문이다. 즉 다음에 탐색해야할 P의 요소는 P[2] 가 되며 T의 요소는 이전에 불일치가 발생한 부분인 T[6]이 된다.

 

이를 일반화한 절차는 다음과 같다.

 

① 길이가 각각 N, M 인 문자열 T와 P에 대해 탐색을 진행, 리스트 L에 문자열 P가 등장하는 모든 위치를 담는다.

 

② T와 P의 초기 인덱스 i, j는 각각 0으로 초기화

 

③ T[i]와 P[j] 가 같다면 두 인덱스를 각각 +1 

    => 만약 그 결과 j가 M이 됐다면(모든 문자가 일치했다면) 찾아낸 구간의 시작위치(i - M)를 리스트 L에 append

    => j를 P[0~j-1] 구간의 접두사/접미사의 길이로 변경. 반복되는 부분을 생략하고

        그 다음 요소부터 검사하기 위함

 

④ T[i]와 P[j] 가 다르다면

    => 만약 j가 0이라면(P문자열의 시작부터 일치하지 않았다면) T[i] 로 시작하는 문자열과는 일치할 수 없기 때문에

         i += 1

    => j를 P[0~j-1] 구간의 양 끝의 가장 긴 반복문자열(위 예시 기준 AB) 의 길이로 설정. 반복되는 부분을 생략하고

        그 다음 요소부터 검사하기 위함

 

⑤ i의 인덱스가 N 이상일 경우 더이상 탐색할 수 없기 때문에 작업 종료

 

⑥ 리스트 L에 담긴 숫자들이 문자열 P가 등장한 모든 인덱스를 나타내며 L의 길이가 P가 나타난 횟수가 된다.

 

 

2. LPS(Longest Proper prefix and Suffix) 테이블

 KMP 알고리즘의 각 단계는 기본적으로 i가 움직이거나 문자열 P의 비교 시작 위치가 움직이기 때문에 O(N+M)의 시간복잡도를 보인다.  다만 여기에는 하나의 전제가 필요하다.  바로 j를 P[1~j-1] 의 접두사/접미사 길이로 변경해주는 작업이 O(1)이어야 한다는 것이다.  물론 정말로 O(1)로 이 작업을 수행할 수는 없지만, 알고리즘을 수행하는 반복문 밖에서 O(M)의 시간복잡도로 LPS테이블을 구해두는 전처리를 하는 것으로 반복문 내에서는 O(1)의 시간복잡도를 보일 수 있다. LPS 테이블을 구하는 절차는 다음과 같다.

 

① 먼저 dp = [0] * (m+1) 으로  LPS 테이블 초기화

② i를 P 문자열의 첫 위치 0으로 초기화

③ P문자열의 j 번째 요소(j=1~m-1) 비교 (④~⑤ 반복)

④ P[i] == P[j] 라면 i를 1 증가시키고 dp[j] = i  (반복구간의 길이가 증가)

⑤ P[i] != P[j] 일 경우

    => 1) i가 0이라면 애초에 반복구간이 아직 존재하지 않기 때문에 단순히 pass

    => 2) i가 0보다 크다면 i를 0이되거나 P[i] == P[j] 가 될 때까지 이전에 P[j]와 일치했던 구간으로 이동 (i = dp[i-1])

⑥ 작업이 모두 끝나면 dp[k] 는 P[1~k] 구간의 LPS값이 된다. 

 

 

3. 구현

 지금까지의 내용을 토대로 실제로 KMP 알고리즘으로 문자열 탐색 문제(https://www.acmicpc.net/problem/1786)를 해결한 코드는 다음과 같다.  

 

import sys

input = sys.stdin.readline


def sol1786():
    # 전체 문자열 T
    T = input().replace('\n', '')
    
    # 찾을 문자열 P
    P = input().replace('\n', '')
    
    # 문자열 T, P의 길이 n, m
    n, m = len(T), len(P)

    # LPS 테이블
    dp = [0] * (m + 1)
    
    # P의 첫 위치이자 suffix의 길이
    i = 0
    
    # dp[j] 는 P[:j+1]의 LPS값
    for j in range(1, m):
        # 만약 P[i]와 P[j] 가 다르고 0보다 크다면
        # P[i]==P[j]가 될 때까지 i를 이전에 suffix가 이어졌던 부분까지 이동
        while i > 0 and P[i] != P[j]:
            i = dp[i-1]
            
        # P[i]와 P[j]가 같다면 suffix의 길이를 1 증가
        # dp[j] 에 suffix의 길이를 저장
        if P[i] == P[j]:
            i += 1
            dp[j] = i

    # 문자열 P가 발견된 위치를 모두 저장할 리스트
    answer = []
    
    # 문자열 T, P의 탐색 위치
    i, j = 0, 0
    
    # i가 문자열 T의 길이에 도달하기 전 까지 반복
    while i < n:
        # T[i]와 P[j] 가 같다면 두 인덱스 모두 1씩 증가
        if T[i] == P[j]:
            i += 1
            j += 1
            
            # 인덱스가 증가한 결과 j가 m에 도달했다면
            # P와 일치하는 문자열을 발견한 것이기 때문에 answer에 append
            # j는 LPS 테이블을 참조하여 다음 탐색 위치(dp[j-1])로 이동
            # 다음 탐색에서는 이미 일치할 것을 알고있는 부분을 생략하고 탐색
            if j == m:
                answer.append(i-m+1)
                j = dp[j-1]
                
        # T[i] 와 P[j] 가 다르다면
        else:
            # 만약 P[0] 부터 일치하지 않았다면 T[i]와의 비교는 무의미하기 때문에 i += 1
            if j == 0:
                i += 1
                
            # j는 LPS 테이블을 참조하여 다음 탐색 위치로 이동
            j = dp[j - 1]
            
    # 문자열 P가 등장한 횟수와 위치를 출력형식에 맞춰 반환
    return '\n'.join(map(str, [len(answer), ' '.join(map(str, answer))]))

 

 

※ LPS 테이블 주의사항

 LPS 테이블을 생성할 때, 처음에는 P[i] != P[j] 일 경우 i를 0으로 초기화후 다시 비교하는 방식을 사용했지만 오답이 나왔다. 이 방식의 문제는 aacaaa 와 같은 문자열에 대해 LPS 테이블을 생성할 때 발생한다. 위 코드처럼 정상적인 방식으로 LPS 테이블을 생성할 경우 0 1 0 1 2 2 가 된다.  하지만 P[i] != P[j] 일 때 i를 0으로 초기화하고 다시 비교할 경우, aacaa 까지는 0 1 0 1 2 로 동일하지만, i가 2인 상태에서 P[2] != P[5] 로 i가 0으로 초기화되어 다시 비교하면 P[0] == P[5]로 dp[5]가 1이 되어버린다.  잘못 구현한 LPS 테이블을 구하는 코드는 다음과 같다.

dp = [0] * (m + 1)
i = 0
for j in range(1, m):
    if P[i] == P[j]:
        dp[j] = dp[j-1] + 1
        i += 1
    else:
        if P[j] == P[0]:
            dp[j] = i = 1
        else:
            i = 0