수달씨의 개발공간

📌 KMP란?

KMP(Knuth-Morris-Pratt) 알고리즘은 부분 문자열 검색(substring search)을 위한 알고리즘으로, 시간 복잡도 **O(N + M)**으로 매우 효율적입니다.

KMP는 비교 중 매칭 실패 시 불필요한 반복을 피하기 위해 "접두사-접미사 일치 정보"를 사전에 계산하여 사용합니다.

🔍 KMP의 핵심 아이디어

• 문자열 haystack에서 needle을 찾는 문제
• 부분 일치가 발생했을 때, 앞으로 돌아가지 않고 재사용할 수 있는 패턴을 저장
• 이때 사용하는 것이 LPS 배열 (Longest Prefix Suffix)

🧠 LPS 배열이란?

LPS(Longest Prefix Suffix) 배열은 자기 자신 내에서 접두사와 접미사가 일치하는 최대 길이를 저장하는 배열입니다.

예시: needle = "a b c d a b d"

index:   0 1 2 3 4 5 6
char:    a b c d a b d
LPS:     0 0 0 0 1 2 0

• LPS[5] = 2 → 앞에서 "ab"와 일치하는 접두사/접미사가 존재함

✅ KMP 알고리즘 구현 (TypeScript)

function computeLPS(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;
}

export function kmpSearch(haystack: string, needle: string): number {
  if (needle === "") return 0;

  const lps = computeLPS(needle);
  let i = 0; // haystack pointer
  let j = 0; // needle pointer

  while (i < haystack.length) {
    if (haystack[i] === needle[j]) {
      i++;
      j++;
    }

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

  return -1;
}

📈 시간 및 공간 복잡도

항목 복잡도 설명

✅ KMP의 장점

• 모든 케이스에서 최악의 경우에도 선형 시간 보장
• needle이 반복되는 경우에 유리함
• 보안, 컴파일러, 문자열 매칭 시스템에서 자주 사용됨