APSS 스터디에서 코딩테스트 준비를 하고 있던 중, 제일 많이 나올 것 같으면서 한번쯤은 마스터하고 넘어가야할 챕터를 맞이했습니다. 거의 50프로이상 출제되는 것 같은 문제인데요. 문자열 탐색 문제입니다.

알고리즘 문제해결전략 책에서 20장에 있는 문자열 챕터입니다.

용어

• 부분문자열(substring)
• 접두사(prefix)
• 접미사(suffix)

문자열 검색 문제

주어진 긴 '짚더미(haystack)' 문자열 H가 '바늘(needle)' 문자열 N을 부분 문자열을 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제를 문자열 검색 문제라고합니다.

문자열 검색을 해결하는 가장 간단한 방법으로는 찾고자하는 N문자열을 한 칸씩 움직이면서 H문자열과 비교하는 방법입니다. 아래코드와 같이요.

def naiveSearch(H:str, N:str):
  ret = []
  for begin in range(len(H) - len(N) + 1):
    matched = True
    for i in range(len(N)):
      if H[begin + i] != N[i]:
        matched = False
        break
        
    if mathced:
		ret.append(begin)
        
  return ret

일치하는지 하나하나 확인하면서 중간에 일치하지않는 문자가 존재할 경우 멈추고 N문자열을 한칸 이동시키고 다시 비교를 시작합니다. 위 알고리즘도 충분히 효율적으로 보이지만 특정 형태의 입력에 대해서는 엄청나게 비효율적입니다.

입력
H : AAAAAAAAAAB
N : AAAAAB

위와 같은 입력이 주어질 때 아래와 같은 비효율적인 연산이 수행됩니다.

|AAAAAAAAAAB
|AAAAAB 

A 5번 비교 후

A|AAAAAAAAAB
 |AAAAAB 

또 동일하게 A 5번 비교

위와 같이 탐색을 진행할 경우, O(len(H) x len(N))의 최악의 복잡도를 생성하게됩니다. 이러한 비효율적인 탐색을 극복하기 위해 나온 알고리즘이 KMP알고리즘입니다.
구현이 조금 다소 이해하기 어렵지만 개념자체는 생각보다 단순합니다.

KMP 알고리즘

KMP(커누스 모리스 프랫 3명의 사람이 같이 만들어서 KMP)알고리즘을 먼저 간단히 설명해보면 처음 비교할 때, 일치했던 부분문자열의 정보를 이용하여 불필요한 비교 즉, 어차피 틀릴걸 아는 부분은 건너뛰어버리는 원리를 이용합니다.

(예제 입력)
H: AABAABEDSDFSDF
N: AABAABAC

다음과 같은 예제 입력을 예시로 들어보겠습니다.

AABAAB|EDSDFSDF
AABAAB|AC

아마 하나하나 문자를 비교하다보면|(파이프라인)까지 비교가 일치할 것입니다. 중요한 것은 다음에 어떤 행동을 취하느냐입니다.

AABAAB|EDSDFSDF
   AAB|AABAC

위와 같이 H의 다음 문자에서부터 다시 비교를 시작하는 것이 아니라 4번째 인덱스의 문자(A)부터 N을 옮겨서 비교를 시작합니다. 비교할 때도 N의 첫문자부터 비교하는 것이아니라 일치했던 부분은 제외하고 AAB이후부터 비교를 시작합니다.

AABAABEDSDFSDF
      AABAABAC

AABAABEDSDFSDF
              AABAABAC

그리고 이어서 진행되는 탐색의 두 단계를 보면 일치하는 부분이 없기 때문에 빠르게 넘어가게됩니다.

다소 설명에 비약이 많았습니다.(설명의 한계가 있네요) 구현을 보면 조금더 이해하기 편할 것 같습니다.

KMP알고리즘에서는 몇 개의 문자가 매칭이 되었을 때, 어디서부터 다시 탐색을 하는지를 알려주는 부분 일치 테이블을 어떻게 구하느냐도 매우 중요합니다.

부분 일치 테이블이 무엇인지 차근차근 알아보겠습니다.

부분 일치 테이블

정의부터 말하자면 탐색할 문자열의 특정인덱스 i까지 매칭이 되었을 때, 어디서부터 다시 탐색을 시작하면 되는지를 알려주는 테이블을 의미합니다.

탐색할 문자열만으로 미리 연산이 가능해서 총 복잡도에 큰 영향을 주지않습니다.
아래와 같은 탐색할 문자열을 가지고 부분 일치 테이블을 만들어 보겠습니다.

# 각 매칭에 대한 접미사와 접두사가 같은 부분 문자열의 길이
pi = [0, 0, 0, 0, 0, 0, 0, 0] 
문자 하나 매칭이 되었을 때, 다음 문자부터 탐색을 진행하면 됩니다.
A|ABAABAC
pi[0] = 0
AA|BAABAC
pi[1] = 1
AAB|AABAC
pi[2] = 0
AABA|ABAC
pi[3] = 1
AABAA|BAC
pi[4] = 2
AABAAB|AC
pi[5] = 3
AABAABA|C
pi[6] = 4

자 pi 배열에는 어떤 값이 들어가는 것 같나요? 접미사와 접두사가 같은 문자열의 최대길이를 의미합니다. 말로만 하면 잘 와닿지 않으니 예를 보시죠
A // // 0
AA // A // 1
AAB // // 0
AABA // A // 1
AABAA // AA // 2
AABAAB // AAB // 3
AABAABA // AABA // 4

즉, 매칭되는 길이마다 접두사와 접미사가 같은 부분 문자열을 찾아서 그 길이 중 가장 긴 길이를 구하는 과정입니다. 해당 길이를 알고 있으면 어디서부터 탐색을 해야할 지 정할 수 있기 때문이죠.

위 pi 배열을 구하는 방법을 살펴보겠습니다.

def get_partial_match(N:str):
  pi = [0] * len(N)
  for begin in range(1, len(N)):
    for i in range(len(N) - begin):
      if N[begin + i] == N[i]:
        break
      pi[begin + i] = max(pi[begin + i], i + 1)
  return pi

위 식을 반복문 하나씩 따라가다보면 아래와 같이 pi를 채우려고 하는 것을 볼 수 있습니다.

AABAABAC
 AABAABA : begin = 1  pi[1+0] = 1
  AABAAB : begin = 2  
   AABAA : begin = 3  pi[3+0] = 1, pi[3+1] = 2, pi[3+2] = 3, pi[3+3] = 4
    AABA : begin = 4  pi[4+0] = 1
     AAB : begin = 5  
      AA : begin = 6  pi[6+0] = 1
       A : begin = 7  

위와 같이 부분 일치 테이블을 구하면 O(N^2)의 복잡도가 걸립니다.

KMP 알고리즘을 부분일치테이블에도 비슷하게 적용가능합니다. 한번 해보죠

def get_partial_match_with_KMP(N:str):
    pi = [0] * len(N)
  	begin = 1
    matched = 0
    while begin + matched < len(N):
      if N[begin + matched] == N[matched]:
        matched += 1
        pi[begin + matched - 1] = matched
        break
        
      if matched == 0:
        begin += 1
      else:
        begin += matched - pi[matched - 1]
        matched = pi[matched - 1]
    return pi

[실행과정]

AABAABAC
 A_      begin = 1, pi[1] = 1
  _      begin = 2
   AABA_ begin = 3, pi[3] = 1, pi[4] = 2, pi[5] = 3, pi[6] = 4
      A_ begin = 6

kmp를 적용하면 위와 같이 부분 일치 테이블을 O(N) 복잡도로 해결이 가능합니다.

이제 위에서 만들어지 함수를 사용해서 KMP알고리즘 전체를 구현해보겠습니다.

def kmp_search(dummy:str, target:str):
  ret = []
  length_of_dummy = len(dummy)
  length_of_target = len(target)
  
  begin = 0
  matched = 0
  
  match_table = get_partial_match_kmp(target)
  while begin <= length_of_dummy - length_of_target:
    if matched < length_of_target and dummy[begin + matched] == target[matched]:
      matched += 1
      if matched == length_of_target:
        ret.append(begin)
    else:
      if macthed == 0:
        begin += 1
      else:
        begin += matched - match_table[matched - 1]
        matched = match_table[matched - 1]
  return ret

위 알고리즘의 실행과정을 시각적으로 살펴보고 이번 포스트는 마무리해보겠습니다.

dummy: AABAABEDSDFSDF
target: AABAABAC

AABAABEDSD
AABAAB_
   AAB_
      _
       _
        _

위와 같이 O(M + N)만에 문자열 탐색이 가능하게됩니다.

• 부분 일치 테이블 생성 O(N)
• KMP알고리즘을 통한 탐색 O(M)
  합치면 위와 같은 결과가 나옵니다.