[바미] Pattern matching algorithms - Knuth-Morris-Pratt 알고리즘 구현하기.

Knuth-Morris-Pratt?

Knuth-Morris-Pratt 알고리즘은 문자열 검색 알고리즘 중 하나로, 특정 문자열에서 패턴 문자열을 찾는 알고리즘이에요.

이 알고리즘은 패턴 문자열의 길이와 검색 문자열의 길이에 비례하는 시간복잡도를 가져서 대용량의 문자열에서 효율적으로 검색할 수 있죠.

 

동작 방식

1. 패턴 문자열을 전처리하여 접두사(prefix)와 접미사(suffix)의 최대길이를 구해요.
2. 검색 문자열을 순회하며 패턴 문자열을 비교해요.
3. 만약 일치하지 않는 문자가 있다면, 해당 문자가 포함된 접미사와 접두사를 이용하여 패턴 문자열을 이동시켜요.
4. 이동한 패턴 문자열과 검색 문자열을 다시 비교해줘요.
5. 일치하지 않는 문자가 없을 때까지 위 과정을 반복해요.

그럼 이제 구현해볼까요?

---

코드 구현

function KMP(text, pattern) {
  const n = text.length;
  const m = pattern.length;

  // 1. 패턴 문자열을 전처리하여 접두사(prefix)와 접미사(suffix)의 최대길이를 구합니다.
  const pi = computePrefix(pattern);

  let i = 0; // text를 순회할 인덱스
  let j = 0; // pattern을 순회할 인덱스

  while (i < n) {
    // 검색 문자열과 패턴 문자열이 일치하는 경우
    if (pattern[j] === text[i]) {
      // 패턴 문자열을 한 칸 이동합니다.
      i++;
      j++;
      // 패턴 문자열을 모두 찾은 경우
      if (j === m) {
        return i - j; // 시작 인덱스 반환
      }
    } else if (j > 0) {
      // 일치하지 않는 문자가 있다면, 해당 문자가 포함된 접미사와 접두사를 이용하여 패턴 문자열을 이동시킵니다.
      j = pi[j - 1];
    } else {
      // 일치하지 않는 문자가 있지만, 이전까지 일치한 문자열이 없는 경우
      i++;
    }
  }

  return -1; // 찾지 못한 경우
}

function computePrefix(pattern) {
  const m = pattern.length;
  const pi = new Array(m); // 접두사(prefix)와 접미사(suffix)의 최대길이를 저장할 배열

  let j = 0; // 패턴 문자열을 순회할 인덱스
  pi[0] = 0; // 첫 번째 문자열의 최대길이는 0입니다.

  for (let i = 1; i < m; i++) {
    // 접두사와 접미사가 일치하는 경우
    while (j > 0 && pattern[j] !== pattern[i]) {
      // 이전에 일치한 문자열이 있다면, 해당 문자열의 최대길이를 구합니다.
      j = pi[j - 1];
    }
    // 접두사와 접미사가 일치하는 경우
    if (pattern[j] === pattern[i]) {
      // 이전에 일치한 문자열의 최대길이보다 1을 더한 값을 저장합니다.
      pi[i] = j + 1;
      j++;
    } else {
      pi[i] = 0;
    }
  }

  return pi;
}

코드 설명

KMP 함수

KMP 알고리즘의 핵심은 패턴 문자열의 접두사와 접미사를 이용하여 패턴 문자열을 더 빠르게 이동시키는 것에 있기 때문에

KMP함수도 이와 동일하게 동작하게 작성했어요.

 

예를 들어, 패턴 문자열이 "abcabc"이라면 이 문자열의 접두사와 접미사는 다음과 같게 되죠.

접두사(prefix): "", "a", "ab", "abc", "abca", "abcab"
접미사(suffix): "", "c", "bc", "abc", "babc", "ababc"

이때, 접두사와 접미사가 일치하는 가장 긴 길이를 구하면 다음과 같은데요.

"", 0
"a", 0
"ab", 0
"abc", 1
"abca", 0
"abcab", 2

위의 결과를 토대로, 패턴 문자열을 이동시킬 때 일치하지 않는 문자열이 나온 경우, 해당 문자열보다 짧은 일치하는 접두사와 접미사를 이용하여 패턴 문자열을 이동시켜주죠.

 

computePrefix함수

KMP 알고리즘의 구현을 위해 사용되는 함수인 computePrefix(pattern) 함수는, 주어진 패턴 문자열 pattern에서 각 위치에서의 접두사와 접미사의 일치하는 길이를 계산하는 함수에요. 이 함수는 패턴 문자열 pattern의 길이 m과 pi 배열을 생성해요.

pi 배열은 패턴 문자열의 각 위치에서의 접두사와 접미사의 일치하는 길이를 저장하는 배열인데 pi[0]은 항상 0이죠.

이후에 패턴 문자열의 각 위치에서, 현재 위치 이전의 문자열들의 접두사와 접미사 중 가장 긴 일치하는 길이를 계산하여 pi 배열에 저장하고 있어요.

KMP(text, pattern) 함수는, 주어진 텍스트 문자열 text에서 패턴 문자열 pattern을 검색하여 시작 인덱스를 반환하는 함수에요.

이 함수는 먼저 computePrefix 함수를 사용하여 패턴 문자열 pattern에서 각 위치에서의 접두사와 접미사의 일치하는 길이를 계산해요.

그 후, text 문자열과 pattern 문자열을 순회하면서 일치하지 않는 문자열이 나올 때, 패턴 문자열을 이동시키는 것을 반복하게 되죠.

이동 거리는 pi 배열을 이용하여 계산하고 있어요.

 

KMP 알고리즘에서 검색 문자열과 패턴 문자열이 일치하는 경우, 패턴 문자열을 한 칸 이동하게 되는데 패턴 문자열을 모두 찾은 경우에는 시작 인덱스를 반환해줘요.

그 이유는 이전에는 j 인덱스를 이용하여 패턴 문자열의 일치 여부를 판단했는데, 이번에는 j 인덱스를 이용하여 패턴 문자열이 일치하지 않는 위치를 찾아낸 경우, 해당 위치부터 다시 패턴 문자열을 검색하기 때문이에요.

즉, 검색 문자열과 패턴 문자열의 일치 여부를 판단하는 j 인덱스를 이동하면서, 패턴 문자열을 찾은 경우에는 시작 인덱스를 반환하고, 찾지 못한 경우에는 -1을 반환하게 됩니다.

---