KMP 알고리즘은 문자열 검색을 어떻게 최적화하나요?

KMP 알고리즘은 문자열 검색에서 불일치가 발생했을 때 이미 비교한 정보를 활용해 패턴을 처음부터 다시 비교하지 않도록 최적화합니다. 핵심은 패턴의 접두사와 접미사가 일치하는 길이를 저장한 실패 함수(LPS, pi 배열)입니다.

핵심 개념

• 일반 검색은 불일치 시 시작 위치를 한 칸 옮기고 패턴 첫 글자부터 다시 비교해 최악 O(nm)이 될 수 있습니다.
• KMP는 패턴 내부의 반복 구조를 이용해 건너뛸 수 있는 비교를 계산합니다.
• 텍스트 길이 n, 패턴 길이 m에 대해 O(n + m)에 검색합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

function buildPi(pattern) {
  const pi = Array(pattern.length).fill(0);
  let j = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (j > 0 && pattern[i] !== pattern[j]) j = pi[j - 1];
    if (pattern[i] === pattern[j]) pi[i] = ++j;
  }
  return pi;
}

function kmp(text, pattern) {
  const pi = buildPi(pattern);
  const found = [];
  let j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = pi[j - 1];
    if (text[i] === pattern[j]) {
      if (j === pattern.length - 1) {
        found.push(i - pattern.length + 1);
        j = pi[j];
      } else j++;
    }
  }
  return found;
}

실무에서 주의할 점

• pi 배열 의미를 '현재 위치까지의 문자열에서 접두사=접미사 최대 길이'로 정확히 이해해야 구현이 안정적입니다.
• 패턴이 빈 문자열인 경우의 정책을 별도로 정해야 합니다.
• 대부분의 실무 단순 검색은 언어 내장 함수가 최적화되어 있으므로 직접 KMP가 필요한지는 확인해야 합니다.

실무 적용 가이드

• 알고리즘 문제, 대용량 로그 패턴 검색, 반복 문자열 분석에서 유용합니다.
• 패턴이 하나가 아니라 여러 개면 Aho-Corasick 같은 알고리즘을 검토합니다.
• 디버깅할 때는 pi 배열을 직접 출력해 패턴 구조와 맞는지 확인합니다.

함께 연결해서 보면 좋은 키워드

KMP, String Search, Prefix Function, LPS

정리

KMP 알고리즘은 문자열 검색에서 불일치가 발생했을 때 이미 비교한 정보를 활용해 패턴을 처음부터 다시 비교하지 않도록 최적화합니다입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.