왜 패턴 매칭이 따로 필요한가

긴 텍스트 안에서 특정 문자열(찾으려는 짧은 문자열을 패턴, pattern이라 부른다)이 어디에 등장하는지 찾는 문제는 문서 편집기의 “찾기” 기능, 웹 브라우저의 페이지 내 검색, DNA 염기서열에서 특정 패턴 찾기처럼 실생활 곳곳에 있다. 배열이나 리스트에서 원소 하나를 찾는 것과 달리, 문자열 검색은 “패턴 전체가 연속으로 일치하는 시작 위치”를 찾아야 한다는 점이 다르다. 가장 단순하게 접근하면 텍스트의 모든 위치에서 패턴을 하나하나 대조해 보면 되지만, 이 방식은 텍스트나 패턴에 반복되는 문자가 많을 때 같은 비교를 쓸데없이 반복하게 된다.

쉽게 말하면: 텍스트라는 긴 문장에서 패턴이라는 짧은 단어가 어디 있는지 찾는 문제이며, 어떻게 하면 같은 자리를 두 번 비교하지 않고 빠르게 찾을 수 있는지가 핵심이다.

나이브 문자열 검색 — 한 칸씩 밀며 전부 비교

나이브 문자열 검색(naive string matching)은 텍스트의 시작 위치를 한 칸씩 옮겨가며, 매번 패턴을 처음부터 끝까지 전부 대조하는 가장 직관적인 방법이다. 텍스트 길이를 $n$, 패턴 길이를 $m$이라 하면, 각 시작 위치에서 최대 $m$번 비교하고 시작 위치 후보는 $n - m + 1$개이므로 최악의 경우 시간 복잡도는 $O(n \times m)$이다.

NaiveSearch(텍스트 T, 패턴 P):
  n = T의 길이, m = P의 길이
  s = 0부터 (n - m)까지 하나씩 증가시키며 반복:
    j = 0
    T[s+1]부터 시작해 P[1]부터 하나씩 비교하며 j를 늘린다
    j가 m이 될 때까지 모두 일치하면 위치 (s+1)에서 매칭 성공
    중간에 불일치하면 이번 s는 실패, 다음 s로 넘어간다(비교했던 내용은 모두 버림)

작은 예시로 추적하기

텍스트 T = ABABCABABC(10글자), 패턴 P = ABABC(5글자)로 나이브 검색을 추적한다. 시작 위치(1-인덱스 기준)를 하나씩 옮기며 비교 횟수를 센다.

총 비교 횟수: 16회, 매칭 성공 위치는 1과 6이다.

3번째 줄(시작 위치 3)을 보면, AB까지는 일치했는데도 세 번째 문자에서 실패하는 순간 그동안의 일치 정보를 모두 버리고 시작 위치만 하나 옮겨서 처음부터 다시 비교한다. 그런데 텍스트의 AB 부분은 패턴의 AB 부분과 이미 일치를 확인했던 조각이다. 이 조각 정보를 버리지 않고 재활용할 수 있다면 비교 횟수를 줄일 수 있는데, 이 아이디어를 구체화한 것이 KMP 알고리즘이다.

자주 틀리는 점: 나이브 검색의 시간 복잡도를 $O(n)$으로 착각하기 쉽다. 최선의 경우(첫 글자부터 계속 불일치)에는 $O(n)$에 가깝지만, 패턴에 반복 문자가 많고 텍스트도 그 문자로 가득할 때(예: 텍스트가 전부 AAAA...A이고 패턴도 AAAB인 경우)는 매번 거의 끝까지 비교하다 마지막에 실패하는 일이 반복되어 $O(n \times m)$에 가까워진다.

KMP 알고리즘 — 실패한 지점의 정보를 재활용한다

KMP(Knuth-Morris-Pratt) 알고리즘은 패턴 자기 자신의 구조를 미리 분석해 두어, 텍스트를 비교하다 실패하더라도 텍스트 포인터는 뒤로 되돌리지 않고 패턴 포인터만 적절한 위치로 옮겨 다시 비교를 이어가는 방법이다. 이 사전 분석 결과를 실패 함수(failure function) 또는 부분 일치 테이블(partial match table)이라 부르며, 흔히 $\pi$(파이) 배열로 표기한다.

• $\pi[i]$: 패턴의 앞부분 $P[1..i]$에서, 자기 자신을 제외한 가장 긴 “접두사(prefix)이면서 동시에 접미사(suffix)인 부분 문자열”의 길이.
  • 접두사(prefix): 문자열의 맨 앞에서부터 이어지는 부분 문자열. 예를 들어 ABAB의 접두사는 A, AB, ABA, ABAB다.
  • 접미사(suffix): 문자열의 맨 뒤에서부터 이어지는 부분 문자열. ABAB의 접미사는 B, AB, BAB, ABAB다.
  • “자기 자신을 제외한”이라는 조건 때문에, $P[1..i]$ 전체와 똑같은 것은 접두사·접미사로 세지 않고 그보다 짧은 것 중 가장 긴 것을 찾는다.

실패 함수를 손으로 계산하기

패턴 P = ABABC(길이 5)의 실패 함수를 각 자리마다 계산한다.

실패 함수 $\pi$ = [0, 0, 1, 2, 0]

$\pi[4]=2$가 의미하는 바를 풀어 보면, 패턴의 앞부분 ABAB를 비교하다가 다섯 번째 글자에서 실패했을 때 “이미 확인한 ABAB 안에 스스로 반복되는 AB 구조가 있으니, 처음부터 다시 볼 필요 없이 이미 일치했던 AB 부분(길이 2)은 그대로 두고 그다음 글자부터 비교를 이어가도 된다”는 뜻이다.

쉽게 말하면: 실패 함수는 “여기서 실패하면 패턴 포인터를 몇 번째 자리로 되돌리면 되는지”를 패턴 자체의 반복 구조에서 미리 계산해 둔 표다.

KMP 검색 과정 추적

같은 텍스트 T = ABABCABABC, 패턴 P = ABABC, 실패 함수 $\pi$ = [0, 0, 1, 2, 0]으로 KMP 검색을 추적한다. $i$는 텍스트 위치, $j$는 패턴 위치를 가리킨다.

KMP(텍스트 T, 패턴 P, 실패함수 π):
  i = 1, j = 1
  T의 끝까지 반복:
    만약 T[i] == P[j]이면 i와 j를 각각 1씩 늘린다
    만약 j가 패턴 길이보다 커지면: 위치 (i - j)에서 매칭 성공. j = π[j-1]로 되돌린다
    그렇지 않고 T[i] != P[j]이면서 j > 1이면: j = π[j-1]로 되돌리고 i는 그대로 둔 채 다시 비교한다
    그렇지 않고(j = 1인데도 불일치) i만 1 늘린다

앞서 위치 1에서 매칭을 찾은 것 외에, 8단계 근처에서 재시도가 이어지지만 실제로는 6단계에서 시작한 매칭 시도가 이어지고 있는 것이다. 이 표에서 6~9단계는 사실 “텍스트 위치 6에서 시작하는 패턴 매칭”을 이어가는 과정이며, i=6부터 j가 3, 4, 5까지 진행하다 실패한 뒤 되돌림을 거쳐 다시 진행해 최종적으로 어디까지 도달하는지는 표를 한 단계 더 이어가면 다음과 같다.

실제로 온전한 추적표를 이어가면(위 표의 8~10단계 사이 되돌림 과정을 지나) 텍스트 위치 6에서 시작한 두 번째 매칭도 ABABC와 완전히 일치해 위치 6에서도 매칭 성공이 확인된다. 이는 나이브 검색에서 확인한 매칭 위치(1과 6)와 정확히 같은 결과다.

핵심은 비교 횟수다. 이 추적 전체에서 텍스트 포인터 $i$는 1부터 11까지 단조롭게 커지기만 하고 절대 되돌아가지 않는다. 되돌아가는 것은 패턴 포인터 $j$뿐이며, $j$가 되돌아가는 총량도 지금까지 $j$가 앞으로 나아간 양을 넘지 못한다. 이 성질 덕분에 전체 비교 횟수는 텍스트 길이와 패턴 길이의 합에 비례하는 $O(n+m)$으로 억제된다.

• $n$: 텍스트의 길이.
• $m$: 패턴의 길이(실패 함수를 만드는 데도 $O(m)$이 걸리지만 검색 자체의 $O(n)$에 비해 부담이 작다).

나이브와 KMP 비교

자주 틀리는 점: “KMP는 실패 함수 계산이 있으니 항상 나이브보다 느릴 수도 있다”고 생각하기 쉽다. 실패 함수 계산은 패턴 길이에 비례하는 $O(m)$으로 한 번만 하면 되고, 이후 검색 전체가 $O(n)$으로 끝나므로 총합 $O(n+m)$은 나이브의 $O(n \times m)$보다 항상 같거나 빠르다(점근적으로). 다만 텍스트·패턴이 매우 짧으면 상수 계수 차이로 체감 속도 차이가 크지 않을 수 있다는 점은 실무적 고려사항이다.

핵심 정리

• 나이브 문자열 검색은 시작 위치를 한 칸씩 옮기며 패턴을 처음부터 다시 비교해, 최악의 경우 $O(n \times m)$이 걸린다.
• KMP는 패턴 자신의 접두사=접미사 구조를 실패 함수 $\pi$로 미리 계산해 두어, 실패해도 텍스트 포인터를 되돌리지 않고 패턴 포인터만 적절한 위치로 옮긴다.
• 실패 함수 $\pi[i]$는 $P[1..i]$에서 자기 자신을 제외한 가장 긴 “접두사이면서 접미사인 부분 문자열”의 길이다.
• KMP는 텍스트 포인터가 항상 앞으로만 진행한다는 성질 덕분에 $O(n+m)$의 시간 복잡도를 보장한다.

마무리 복습

참고 자료

• 문자열 패턴 매칭 강의노트 - KMP 알고리즘 개관 (GeeksforGeeks)  — 나이브 검색과 KMP의 의사코드, 실패 함수 계산법, 복잡도 분석을 정리한 자료.
• 국가평생교육진흥원 독학학위제  — 독학사 4단계 알고리즘 과목의 최신 출제기준·평가영역 확인용 공식 안내.