👉 참고할 문제 : BOJ - IOIO

🎯 KMP 알고리즘

백준 브론즈 - 실버 문제를 접할 때 정말 많이 나오는 유형이 문자열 문제이다. 문제의 길이도 짧고, 직관적으로 이해가 가는 문제였기 때문에 어렵게 느껴지지도 않는다. 하지만 메모리 초과나 시간 초과가 무조건 한번씩은 발생한다. 특히 Node.js로 문제를 해결하고자 할 때 문자열을 다루는 내장함수 slice(), splice(), indexOf()가 존재하기 때문에 시간복잡도가 문자열 길이의 곱에 비례하여 O(NM)이 된다.

시간복잡도가 O(NM)인 것을 O(N+M)으로 줄일 수 있는 알고리즘이 바로 KMP 알고리즘이다.

이 KMP 알고리즘의 핵심 키워드는 패턴을 정의해서 했던 비교를 또 하지 않는다. 이다.

💎 패턴을 관리하는 Failure 배열 만들기

우리에게는 검색의 대상이되는 문자열(origin)과, 찾아야하는 패턴의 문자(keyword), 추가적으로 KMP를 위해 추가되는 개념인 failure function이 존재한다.

예를 들어 origin은 전체 길이가 16인 ‘aabcacabcabcacab’이고 찾으려는 패턴 keyword은 길이가 10인 ‘abcabcacab’라고 했을때, 최종 failure fuction은 아래와 같은 배열의 형태를 띈다.

인덱스 0 1 2 3 4 5 6 7 8 9
keyword a b c a b c a c a b
failure -1 -1 -1 0 1 2 3 -1 0 1

이렇게 패턴을 기록하는 이유는 찾고자 하는 keyword가 내부적으로 어떠한 패턴을 가지고 있다면, keyword를 찾기위해 전체 문자열인 origin과 0번 인덱스부터 비교해 나갈때, 서로 다르더라도 다시 처음부터 반복할 필요가 없게 만드는 것이다. 패턴만큼의 비교 인덱스를 건너뛰면 되기 때문이다.

그렇다면 본격적으로 위와 같이 failure 함수를 만들어보는 작업을 해보자.

  • 길이는 keyword와 동일하다.
  • failure[0]의 값은 -1로 초기화한다.
  • 이후 반복문을 통해 keyword 배열을 순회하는데, 이때 중점이 되는 곳은 현재 인덱스의 failure 값이 아니라, 한 칸 앞의 failure 인덱스의 값보다 +1한 keyword의 값을 봐야한다. 그 이유는 failure 함수를 만드는 목적이 keyword의 패턴을 파악하기 위한 것이기 때문이다.

예를 들어 인덱스 값이 4라면 failure[3]이 가지는 값(-1)보다 +1한 값(0)의 keyword 인덱스를 살펴본다. 한마디로 keyword[0]의 값이 keyword[4] 값과 같다면 faulure[3] + 1한 값을 failure[4]에 넣어주면 된다.

💎 Failure 배열을 활용해서 keyword 찾기

이제 본격적으로 origin과 keyword를 첫번째 인덱스부터 비교하기 시작할텐데, 여기서 달라지는 점은 바로, 비교하는 두 값이 다를 때에는 failure 배열을 활용한다는 것이다.

현재 origin은 ‘aabcacabcabcacab’이고 찾으려는 패턴은 keyword ‘abcabcacab’이다. 이제 두 문자열의 첫 인덱스부터 비교를 시작하는데, 만약 keyword와 origin이 달라졌을 경우에 우리가 이미 만들어놓은 failur 배열을 활용해주는 것이다. 현재 m의 값이 1이므로 한칸 앞의 failure[0]번 값을 보자. failure[0]번의 값은 -1이므로, 여기에 1을 더한 값 0이 m의 값이 된다. 즉, m은 다시 0이 되고 n은 여전히 1인채로, 한 칸씩 비교를 계속 해나간다.

🎯 KMP 코드 구현 (JS)

function KMP(origin, keyword) {
  let originalArr = origin.split('');
  let keywordArr = keyword.split('');
  let failureArr = Array(keywordArr.length).fill(-1);

  // failure 배열 세팅
  for (let i = 1; i < keywordArr.length; i += 1) {
    let index = failureArr[i - 1] + 1;
    if (keywordArr[i] === keywordArr[index]) {
      failureArr[i] = index;
    } else {
      failureArr[i] = -1;
    }
  }

  // 비교 시작
  let N = 0;
  let M = 0;
  let count = 0;

  while (N < originalArr.length) {
    if (originalArr[N] === keywordArr[M]) {
      N += 1;
      M += 1;
      if (M === keywordArr.length) {
        count += 1;
        M = failureArr[M - 1] + 1; // 다음 등장을 위해 M을 업데이트
      }
    } else if (M === 0) {
      N += 1;
    } else {
      M = failureArr[M - 1] + 1;
    }
  }

  return count;
}