여러분이 작성한 수만 줄의 소스 코드나 수백 페이지 분량의 방대한 텍스트 문서 안에서 "algorithm"이라는 특정 단어를 찾아야 한다고 가정해 보겠습니다. 문서 뷰어의 'Ctrl + F(찾기)' 기능은 어떻게 그 긴 문서 속에서 눈 깜짝할 새에 단어의 위치를 찾아내는 것일까요? 단순히 긴 글(본문)의 첫 글자부터 찾으려는 단어(패턴)를 하나씩 대조해 보는 브루트 포스(Brute Force) 방식은 최악의 경우 엄청난 시간이 소요됩니다. 1977년, 세 명의 천재 컴퓨터 과학자(Knuth, Morris, Pratt)는 "왜 이미 확인해서 일치했던 글자 정보들을 버리고 매번 처음부터 다시 검사해야 하는가?"라는 합리적인 의문을 품었습니다. 이 질문에서 출발하여, 문자열 탐색의 효율성을 혁명적으로 끌어올린 불세출의 KMP 알고리즘이 탄생하게 됩니다. 오늘은 KMP 알고리즘의 심장이라 불리는 '접두사와 접미사', 그리고 'LPS 배열'의 원리를 낱낱이 해부해 보겠습니다.
1. 브루트 포스(Brute Force) 매칭의 치명적 비효율성
KMP의 위대함을 알기 위해서는 기존 방식의 멍청함을 먼저 깨달아야 합니다. 본문 텍스트가 `A B A B A B C` 이고, 찾으려는 패턴이 `A B A B C`라고 합시다.
- 앞에서부터 4글자 `A B A B`까지는 기분 좋게 일치했습니다.
- 하지만 5번째 글자에서 본문은 `A`, 패턴은 `C`이므로 불일치(Mismatch)가 발생합니다.
- 이때 기존의 단순 탐색은 방금 전까지 힘들게 4글자나 일치시켰던 과거의 정보(A B A B)를 미련 없이 쓰레기통에 버려버리고, 본문의 2번째 글자인 `B`부터 다시 처음부터 패턴을 맞추기 위해 헛수고를 시작합니다.
본문의 길이를 $N$, 패턴의 길이를 $M$이라고 할 때, 이 방식은 최악의 경우 $O(N \times M)$의 처참한 시간 복잡도를 보입니다. 텍스트가 방대해질수록 시스템 성능은 바닥을 치게 됩니다.
2. KMP의 핵심 철학: "과거의 성공을 기억하라"
KMP 알고리즘은 "불일치가 발생하기 직전까지 일치했던 문자열 안에, 이미 반복되는 패턴이 들어있다면 그 부분은 굳이 다시 처음부터 검사하지 말고 건너뛰자(Shift)"는 아이디어에서 출발합니다. 이를 위해 패턴 문자열 자체를 미리 분석하여 LPS (Longest Proper Prefix which is also Suffix) 테이블을 구축해야만 합니다.
2-1. 접두사(Prefix)와 접미사(Suffix), 그리고 LPS
LPS는 '가장 긴 일치하는 접두사와 접미사의 길이'를 의미합니다. 패턴 `A B A B C`를 분석해 보겠습니다. 부분 문자열이 주어졌을 때, 자기 자신을 제외한 맨 앞부분(접두사)과 맨 뒷부분(접미사)이 똑같이 생긴 최대 길이를 적습니다.
- 길이 1 (`A`): 접두사/접미사가 없으므로 LPS는 0
- 길이 2 (`A B`): 접두사 'A', 접미사 'B' (다름) -> LPS는 0
- 길이 3 (`A B A`): 접두사 'A', 접미사 'A' (같음!) -> LPS는 1
- 길이 4 (`A B A B`): 접두사 'A B', 접미사 'A B' (같음!) -> LPS는 2
- 길이 5 (`A B A B C`): 다름 -> LPS는 0
이렇게 만들어진 LPS 배열 `[0, 0, 1, 2, 0]`은 KMP 검색 엔진을 구동하는 완벽한 내비게이션 지도가 됩니다.
3. KMP 매칭 시뮬레이션: 점프의 마법
이제 다시 본문 `A B A B A B C`에서 패턴 `A B A B C`를 찾아봅시다.
- 앞의 4글자 `A B A B`까지는 일치했고, 5번째 `C`에서 불일치가 터졌습니다.
- 일치했던 패턴 `A B A B`(길이 4)의 LPS 값을 표에서 찾아봅니다. 값은 2입니다.
- 이 '2'가 의미하는 바는 엄청납니다. "너희 앞뒤로 'A B'라는 2글자가 이미 반복되어 똑같이 맞춰져 있으니까, 본문의 탐색 포인터를 뒤로 무식하게 되돌리지 말고, 패턴의 앞쪽 2글자는 이미 맞은 셈 치고 패턴의 3번째 글자부터 본문과 이어서 바로 대조해라!"라는 뜻입니다.
결과적으로 KMP 알고리즘은 본문의 탐색 포인터($i$)를 단 한 번도 뒤로 후진(Backtracking)시키지 않고 오직 전진만 시킵니다. $N$개의 텍스트를 한 번만 쭉 훑으면 끝납니다. LPS 테이블을 만드는 시간 $O(M)$과 탐색 시간 $O(N)$을 합쳐, 총 시간 복잡도는 $O(N + M)$이라는 경이롭고 안정적인 선형 시간(Linear Time)으로 극적인 단축을 이뤄냅니다. 바이러스 백신의 시그니처 패턴 검사나 대용량 로그 분석 시스템에서 KMP는 선택이 아닌 필수적인 문자열 탐색의 표준입니다.
1. KMP 알고리즘은 긴 텍스트 속에서 특정 패턴(단어)을 $O(N+M)$의 선형 시간 만에 찾아내는 고속 문자열 탐색 알고리즘입니다.
2. 매칭에 실패했을 때 본문 포인터를 뒤로 후진시키지 않기 위해, 탐색 전에 패턴의 접두사와 접미사의 일치 길이를 미리 계산하여 LPS 배열(Pi 테이블)을 구축합니다.
3. 불일치가 발생하면 이 LPS 지도를 보고 이미 일치하는 부분은 안전하게 건너뛰어(Jump) 불필요한 재검사 연산을 완벽하게 제거하는 것이 속도의 핵심입니다.