비교에 실패했을 때 우리는 무언가를 알게 됩니다. 대부분의 구현은 그 정보를 버립니다.
나이브 서치가 놓치는 것
문자열에서 패턴을 찾는 가장 단순한 방법은 모든 시작 위치에서 처음부터 비교하는 겁니다.
function naiveSearch(text, pattern) {
for (let i = 0; i <= text.length - pattern.length; i++) {
let j = 0;
while (j < pattern.length && text[i + j] === pattern[j]) j++;
if (j === pattern.length) return i;
}
return -1;
}텍스트 길이가 N, 패턴 길이가 M이면 최악 O(N × M)이고, 실패할 때마다 처음으로 돌아가는 비용이 그대로 곱해집니다.
여기서 낭비가 발생하는 지점을 봅니다. 패턴 ABABC를 텍스트와 맞춰보다가 다섯 번째 글자에서 실패했다고 해봅시다. 앞의 네 글자 ABAB는 일치했다는 뜻입니다.
나이브 방식(naive search) 은 이 정보를 버리고 시작 위치를 한 칸만 옮겨 처음부터 다시 비교합니다. 그런데 텍스트의 그 자리에 ABAB가 있다는 것을 우리는 이미 압니다. 패턴의 앞부분 AB가 그 ABAB의 뒤쪽 AB와 같으므로, 두 칸 옮긴 위치에서는 이미 두 글자가 맞아 있는 상태입니다.
실패 함수는 그 정보를 미리 계산해둡니다
KMP 알고리즘(Knuth-Morris-Pratt algorithm) 은 패턴 자체를 먼저 분석합니다. 패턴의 각 위치까지 봤을 때, 접두사이면서 동시에 접미사인 가장 긴 문자열의 길이를 구해둡니다. 이 길이들이 실패 함수(failure function) 입니다.
ABABC의 인덱스 3까지 보면 ABAB입니다. 접두사이면서 접미사인 가장 긴 것은 AB이므로 값은 2입니다. 불일치가 나면 패턴의 2번 위치부터 이어서 비교하면 됩니다.
function buildFailure(pattern) {
const failure = new Array(pattern.length).fill(0);
let len = 0; // 현재까지 일치한 접두사 길이
for (let i = 1; i < pattern.length; i++) {
while (len > 0 && pattern[i] !== pattern[len]) {
len = failure[len - 1]; // 더 짧은 접두사로 후퇴
}
if (pattern[i] === pattern[len]) len++;
failure[i] = len;
}
return failure;
}패턴을 자기 자신과 맞춰보는 구조입니다. 매칭 과정과 형태가 같습니다.
function kmpSearch(text, pattern) {
if (pattern.length === 0) return 0;
const failure = buildFailure(pattern);
let j = 0; // 패턴에서 맞춘 길이
for (let i = 0; i < text.length; i++) {
while (j > 0 && text[i] !== pattern[j]) {
j = failure[j - 1]; // 텍스트는 그대로, 패턴만 이동
}
if (text[i] === pattern[j]) j++;
if (j === pattern.length) return i - pattern.length + 1;
}
return -1;
}이 알고리즘의 특징은 텍스트를 가리키는 i가 한 번도 뒤로 가지 않는다는 점입니다. 텍스트를 한 번만 통과하므로 전체가 O(N + M)입니다. 전처리 O(M)에 매칭 O(N)입니다. 텍스트 백만 자에 패턴 천 자면 나이브 방식은 최악 십억 번, KMP는 백만 번 남짓입니다.
긴 로그 스트림에서 특정 문자열을 계속 찾아야 할 때 이 성질이 쓸모 있습니다. 데이터가 조각으로 나뉘어 들어와도 텍스트를 되돌리지 않으므로, 앞의 조각을 버리고 이어서 비교할 수 있습니다.
해시로 비교하는 방법
라빈-카프 알고리즘(Rabin-Karp algorithm) 은 문자열을 하나씩 비교하는 대신 해시값을 비교합니다.
패턴의 해시를 구해두고, 텍스트에서 같은 길이의 구간마다 해시를 구해 맞춰봅니다. 해시가 다르면 그 구간은 확실히 다르므로 넘어갑니다. 같으면 그때만 실제 문자열을 비교합니다.
구간을 옮길 때마다 해시를 처음부터 계산하면 이득이 없습니다. 롤링 해시(rolling hash) 를 써서 앞 글자를 빼고 뒤 글자를 더하는 방식으로 상수 시간에 갱신합니다.
평균 O(N + M)이고 최악은 해시 충돌이 계속 일어날 때 O(N × M)입니다. 여러 패턴을 동시에 찾는 상황에서는 KMP보다 다루기 편합니다.
파일 동기화 도구가 롤링 해시를 씁니다. rsync는 파일을 일정 크기로 나눠 각 조각의 체크섬을 굴려가며 비교하고, 바뀐 조각만 전송합니다. 문서 사이의 중복 구간을 찾는 표절 검사도 같은 방식입니다.
접두사를 공유하는 트라이
찾을 문자열이 하나가 아니라 수천 개라면 매번 매칭하는 방식은 비효율적입니다. 트라이(trie) 는 문자열 집합을 트리로 만들어 공통 접두사를 한 번만 저장합니다.
cat, car, card를 넣으면 c, a까지는 노드 하나씩만 쓰고 그 뒤에서 갈라집니다.
class Trie {
#root = { children: new Map(), isEnd: false };
insert(word) {
let node = this.#root;
for (const ch of word) {
if (!node.children.has(ch)) {
node.children.set(ch, { children: new Map(), isEnd: false });
}
node = node.children.get(ch);
}
node.isEnd = true; // 단어의 끝 표시
}
// 정확히 일치하는 단어가 있는지
has(word) {
const node = this.#traverse(word);
return node !== null && node.isEnd;
}
// 이 접두사로 시작하는 단어가 있는지
startsWith(prefix) {
return this.#traverse(prefix) !== null;
}
#traverse(str) {
let node = this.#root;
for (const ch of str) {
if (!node.children.has(ch)) return null;
node = node.children.get(ch);
}
return node;
}
}조회 비용이 단어 길이에만 비례합니다. 저장된 단어가 백만 개여도 길이가 열 글자면 열 번의 이동으로 끝납니다. 자동완성이나 사전 검색처럼 접두사 질의가 반복되는 용도에 맞습니다.
대가는 메모리입니다. 노드마다 자식 맵을 들고 있어 해시 집합보다 공간을 많이 씁니다. 접두사 질의가 필요 없다면 Set이 낫습니다.
자동완성 입력창에 트라이를 씁니다. 사용자가 한 글자 칠 때마다 그 접두사로 시작하는 후보만 꺼내면 되기 때문입니다. 라우터가 IP 주소의 앞부분을 보고 다음 홉을 고를 때 쓰는 라딕스 트리도 트라이를 압축한 구조입니다.
무엇을 언제 쓰는가
| 상황 | 선택 |
|---|---|
| 패턴 하나를 한 번 찾음 | 내장 indexOf |
| 패턴 하나를 긴 텍스트에서 반복 | KMP |
| 여러 패턴을 동시에 | 라빈카프 또는 트라이 기반 방식 |
| 접두사 질의가 반복 | 트라이 |
실무에서는 대부분 indexOf면 됩니다. 자바스크립트의 indexOf나 정규식은 엔진 수준에서 최적화되어 있어 직접 구현한 KMP보다 빠른 경우가 많습니다.
참고 자료
- Knuth, D. E., Morris, J. H., & Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2), 323-350.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
다음 편 예고
최대공약수, 소수 판별, 나머지 연산은 그 자체로 문제가 되기보다 다른 문제 안에 조용히 섞여 들어오는 계산들입니다. 마지막 편에서 정리합니다.