[javascript] 문자열 매칭 알고리즘

18 Dec 2023

javascript

이번에는 JavaScript에서 문자열 매칭 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

1. 단순한 방법

가장 단순한 문자열 매칭 알고리즘은 두 문자열을 한 문자씩 비교하는 방법입니다.

function simpleStringMatch(text, pattern) {
  for (let i = 0; i <= text.length - pattern.length; i++) {
    let j;
    for (j = 0; j < pattern.length; j++) {
      if (text[i + j] !== pattern[j]) break;
    }
    if (j === pattern.length) return i; // 매칭된 인덱스 반환
  }
  return -1; // 매칭 실패
}

하지만 이 방법은 문자열이 길어질수록 비효율적입니다.

2. KMP 알고리즘

KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 매칭을 보다 효율적으로 수행하는 알고리즘입니다. 먼저 패턴에 대한 실패 함수를 계산한 다음, 이를 활용하여 텍스트 문자열을 한 번만 훑어 패턴 매칭을 수행합니다.

function computeLPSArray(pattern) {
  let lps = Array(pattern.length).fill(0);
  let len = 0;
  let i = 1;
  while (i < pattern.length) {
    if (pattern[i] === pattern[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }
  return lps;
}

function KMPSearch(text, pattern) {
  let M = pattern.length;
  let N = text.length;
  let lps = computeLPSArray(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; // 매칭된 인덱스 반환
      j = lps[j - 1];
    } else if (i < N && pattern[j] !== text[i]) {
      if (j !== 0) j = lps[j - 1];
      else i = i + 1;
    }
  }
  return -1; // 매칭 실패
}

KMP 알고리즘은 패턴에 대한 실패 함수를 미리 계산하므로 효율적인 문자열 매칭을 수행할 수 있습니다.

JavaScript에서 문자열 매칭 알고리즘을 구현할 때는 매칭 속도 및 메모리 사용량에 유의해야 합니다.

참고 자료

GeeksforGeeks - KMP 알고리즘