KMP 알고리즘이란? Knuth–Morris–Pratt 문자열 검색 이해하기

Knuth–Morris–Pratt, 줄여서 KMP는 Text 안에서 특정 Pattern을 찾는 대표적인 문자열 검색 알고리즘입니다.

KMP의 핵심은 mismatch가 발생했을 때 이전까지 성공했던 비교 정보를 모두 버리지 않는 것입니다.

이를 위해 Pattern을 먼저 분석하여 LPS 배열을 만듭니다.

LPS란?

LPS는 다음을 의미합니다.

Longest Proper Prefix which is also a Suffix

즉, 현재 문자열에서 Prefix이면서 동시에 Suffix인 가장 긴 문자열의 길이를 저장합니다.

예:

Pattern: A B A B A C
LPS:     0 0 1 2 3 0

ABAB에서는 AB가 Prefix이면서 Suffix이므로 LPS 값은 2입니다.

LPS를 사용하는 이유

Pattern의 앞부분이 이미 match된 상태에서 mismatch가 발생했다고 가정합니다.

단순 알고리즘은 다시 처음부터 확인할 수 있지만 KMP는:

j = lps[j - 1]

을 사용해 이전 Match에서 여전히 유효한 부분을 유지합니다.

TypeScript로 LPS 만들기

function buildLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);
  let length = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else if (length !== 0) {
      length = lps[length - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }

  return lps;
}

예를 들어:

ABABCABAB

의 LPS는:

[0, 0, 1, 2, 0, 1, 2, 3, 4]

입니다.

KMP 검색 구현

function kmpSearch(text: string, pattern: string): number {
  if (pattern.length === 0) return 0;

  const lps = buildLPS(pattern);

  let i = 0;
  let j = 0;

  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;

      if (j === pattern.length) {
        return i - j;
      }
    } else if (j !== 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }

  return -1;
}

여기서 i는 Text 위치, j는 Pattern 위치입니다.

KMP의 중요한 특징은 Text의 i가 뒤로 이동하지 않는다는 것입니다.

복잡도

Text 길이를 n, Pattern 길이를 m이라고 하면:

LPS 생성: O(m)
검색:     O(n)
전체:     O(n + m)
공간:     O(m)

반면 Naive Search는 최악의 경우:

O(n × m)

까지 필요할 수 있습니다.

실제 활용

KMP와 String Matching 개념은 다음 영역에서 활용될 수 있습니다.

• 문서 및 문자열 검색
• Log 분석
• DNA Sequence 검색
• 데이터 스트림 Pattern 검색
• 보안 Signature 검색
• 알고리즘 문제와 기술 면접

기술 면접에서 KMP

관련 문제는 다음 형태로 나타날 수 있습니다.

• Find substring
• Find all occurrences
• Build LPS
• Longest prefix that is also suffix
• Repeated substring pattern

코드를 외우는 것보다 LPS가 왜 필요한지를 이해하는 것이 더 중요합니다.

흔한 구현 실수

Mismatch가 발생하고 j > 0이면 i까지 증가시키면 안 됩니다.

다음만 수행합니다.

j = lps[j - 1]

현재 Text 문자를 새로운 Pattern 위치와 다시 비교해야 하기 때문입니다.

정리

KMP는 Pattern 자체의 반복 구조를 이용해 불필요한 비교를 줄이는 문자열 검색 알고리즘입니다.

핵심은 Pattern을 미리 처리하여 LPS 배열을 만드는 것입니다.

Time Complexity: O(n + m)
Space Complexity: O(m)

가장 중요한 아이디어는 mismatch가 발생해도 이전 Match에서 얻은 정보를 모두 버릴 필요가 없다는 것입니다.