KMP (Knuth-Morris-Pratt) 문자열 검색 알고리즘

크래프톤 정글 8기 - 35일 차 TIL

KMP (Knuth-Morris-Pratt) 문자열 검색 알고리즘 정리

문자열 검색 알고리즘 중 하나인 KMP 알고리즘은 텍스트에서 특정 패턴이 존재하는지 빠르게 찾아내기 위한 알고리즘이다. 이 글에서는 KMP 알고리즘의 동작 원리와 핵심 개념인 LPS(Longest Prefix Suffix) 배열을 중심으로 정리하였다.

---

1. KMP 알고리즘의 핵심 아이디어

"문자열 검색 중 일치하지 않으면, 이미 비교한 정보를 활용해 중복 비교를 피한다"

일반적인 완전 탐색은 실패하면 항상 패턴의 처음부터 다시 시작하지만, KMP는 패턴 내의 반복 구조를 이용해 비교 위치를 점프할 수 있다. 이로 인해 최악의 시간복잡도가 O(n + m)으로 매우 효율적이다.

---

2. LPS (Longest Prefix Suffix) 배열

LPS 배열은 KMP의 핵심이다.

LPS[i]의 의미:

• pattern[0...i]까지의 부분 문자열 중
• 접두사 == 접미사인 가장 긴 길이

예: 패턴 "A B C D A B C A"의 LPS 배열은 [0, 0, 0, 0, 1, 2, 3, 1]

i	P[i]	접두사/접미사	LPS[i]	설명
0	A	-	0	항상 0
1	B	A ≠ B	0	일치 없음
2	C	A B ≠ C	0	일치 없음
3	D	A B C ≠ D	0	일치 없음
4	A	A	1	A == A
5	B	A B	2	AB == AB
6	C	A B C	3	ABC == ABC
7	A	A B C A	❌ 1 → ❓	1

LPS 배열 만드는 방법:

1. i = 1, len = 0부터 시작
2. pattern[i] == pattern[len]이면:
   • len++, LPS[i] = len, i++
3. 다르면:
   • len = LPS[len - 1]로 되돌아감 (더 짧은 접두사 시도)
   • len == 0이면 LPS[i] = 0, i++

---

손으로 직접 구한 LPS 예제

예제 1: 패턴 ABABAC

인덱스:   0 1 2 3 4 5
문자:    A B A B A C
LPS:    0 0 1 2 3 0

예제 2: 패턴 ABCABC

인덱스:   0 1 2 3 4 5
문자:    A B C A B C
LPS:    0 0 0 1 2 3

---

3. KMP 문자열 검색 동작 방식

1. i = 0 (text index), j = 0 (pattern index)부터 시작
2. 문자가 일치하면 i++, j++
3. 패턴 끝까지 일치했으면 match 발견 (j == m)
4. 불일치하면:
   • j != 0 → j = LPS[j-1]
   • j == 0 → i++

예시:

Text: ABABACABABABC
Pattern: ABABABC
LPS: [0, 0, 1, 2, 3, 4, 0]

불일치가 발생하면 LPS를 따라 점프하며, 중복 비교 없이 빠르게 다음 후보 위치를 찾는다.

---

4. KMP의 장점

• 항상 O(n + m)의 시간 복잡도
• 전처리 과정은 O(m)
• 매우 안정적이며 실전에서 많이 사용
• 텍스트가 매우 길고 패턴에 반복이 많을수록 효과적

---

5. KMP는 다이나믹 프로그래밍인가?

KMP의 LPS 배열은 패턴 내의 부분 문제를 미리 계산해 저장하는 구조로, 일종의 다이나믹 프로그래밍적 전처리라고 볼 수 있다.

KMP	다이나믹 프로그래밍
부분 일치 정보를 저장	메모이제이션과 유사
점프 위치를 빠르게 찾음	하위 문제 결과 재활용

---

결론

KMP는 고전적이지만 강력한 문자열 검색 알고리즘이다.

• 패턴 내 구조를 전처리하여 불필요한 비교를 피하고,
• 실패 후에도 빠르게 다음 비교를 이어간다.

비록 KMP 알고리즘 보다 더 빠른 알고리즘의 존재로 인해 많이 사용되지는 않지만 다른 알고리즘 보다 구현이 단순하다.