문자열 - KMP 알고리즘

박춘화·2022년 3월 1일
0

Algorithm

목록 보기
4/7

KMP 알고리즘

길이가 M인 문자열 내에 길이가 N인 단어가 있는지 확인하는 알고리즘

단어 내에 동일한 패턴의 문자가 반복될 경우, 이미 확인이 끝난 패턴의 재확인을 피하기 위해 패턴 테이블을 만든다.

패턴 테이블

  • 단어: abcaby
    • 인덱스 0의 경우: 앞에 문자가 없으므로 0
    • 인덱스 1의 경우: a !== b이므로 0
    • 인덱스 2의 경우: a !== c이므로 0
    • 인덱스 3의 경우: a === a이므로 1
    • 인덱스 4의 경우: 이전 인덱스의 문자가 일치하고 b === b이므로 2
    • 인덱스 5의 경우: 이전 인덱스의 문자가 일차하나 c !== y이므로 0
  • 패턴 테이블: [0, 0, 0, 1, 2, 0]
const createPatternTable = (pattern) => {
    const patternLength = pattern.length;

    const patternTable = Array(patternLength).fill(0);

    for (let i = 1; i < patternLength; i++) {
      if (patternTable[i - 1] === 0) {
        if (pattern[0] === pattern[i]) {
          patternTable[i] = 1;
        }
      } else {
        if (pattern[patternTable[i - 1]] === pattern[i]) {
          patternTable[i] = patternTable[i - 1] + 1;
        } else {
          if (pattern[0] === pattern[i]) {
            patternTable[i] = 1;
          }
        }
      }
    }

    return patternTable;
  };

완성된 패턴 테이블을 활용하여 문자열에서 단어를 검색한다.

const KMPAlgorithm = (text, pattern) => {
  const length = text.length;
  const patternLength = pattern.length;
  const table = createPatternTable(pattern);

  let textIndex = 0;
  let tableIndex = 0;
  let counter = 0;
  let answer = -1;

  while (length + tableIndex - textIndex >= patternLength && answer === -1) {
    if (text[textIndex + counter] === pattern[tableIndex + counter]) {
      counter += 1;
      if (tableIndex + counter === patternLength) {
        answer = textIndex - tableIndex;
      }
    } else {
      textIndex = counter > 0 ? textIndex + counter : textIndex + 1;
      tableIndex =
        tableIndex + counter - 1 >= 0 ? table[tableIndex + counter - 1] : 0;
      counter = 0;
    }
  }

  return answer;
};
profile
함께 성장하는 개발자

0개의 댓글