[문자열] KMP 알고리즘

알고리즘 카테고리의 첫 포스팅은, KMP 알고리즘이다.

Knuth, Morris, Pratt 이라는 세 사람의 첫 글자를 따선 만든 알고리즘인데,

쉽게 정의하자면 서로 다른 문자열을 비교하는 알고리즘이라고 보면 된다.

 

예를 들어, 'aaaabbccaab' 라는 문자열이 있을때,

'aab'라는 문자열이 몇번째 인덱스에 있는지 찾고자한다면

어떻게 찾아야 할까?

 

당장 떠오르는 방법은 아마도 'aaaabbccaab'의 첫번째글자와

'aab'의 첫 번째 글자를 비교해서 동일하면,

각각 두번째 글자를 비교하고

또 동일하면 세번째 글자를 비교하고.

만약 세번째에서 동일하지 않다면,

비교의 시작점이었던 'aaaabbccaab'의 두번째 글자로 돌아와서,

다시 'aab'의 첫 번째 글자와 비교를 할 것이다.

 

이 방법의 시간복잡도는, 두 문자열의 길이의 곱에 비례한다.

즉, O(nm)이 된다는 이야기다.

 

만약, 전체 문자열이 10,000,000 개의 글자로 이루어져있고

찾으려는 문자열이 10,000 개라고 한다면

시간 복잡도는...굳이 말하지 않아도 어마어마하게 크다는 것을 알 수 있다. 

 

이러한 편차를 O(n+m)이라는 획기적인 수치로 줄여 줄 수 있는 알고리즘이 바로 KMP 알고리즘이다.

 

사실 이 KMP 알고리즘은 무려 10년 전, 대학생시절 자료구조 수업때 배웠던 내용인데...

'조금만 다른 방향에서 생각해보면, 이렇게나 획기적으로 효율성을 가질 수 있구나'라는

충격적인 깨달음을 나한테 줬던 알고리즘으로,

문자열 비교 === KMP 라고 떠올릴만큼 내 머릿속에는 또렷히 박혀있는 알고리즘이다.

---

설명을 시작해보자.

 

KMP에 대해 설명된 다른 분들의 포스팅을 보면,

prefix와 postfix 개념을 먼저 설명해놓으셨던데...

여기선 그 개념을 몰라도 충분히 KMP를 이해 할 수 있다.

 

KMP의 핵심 기법을 한 줄로 정리해보자면.

"패턴을 정의해서, 했던 비교를 또 하지 않는다."라는 거다.

 

1. 패턴을 관리하는 failure 배열 만들기

KMP와 관련해서 우리는 기본적으로 2개의 문자열을 받는다.

검색의 대상이되는 문자열(origin)과, 찾아야하는 패턴의 문자(keyword).

그리고 여기에 KMP를 위해 추가되는 개념이 'failure funtion'다.

 

예를 들어보자.

 

전체 문자열 origin 은 전체 길이가 16인 'aabcacabcabcacab'이고

찾으려는 패턴 keyword은 길이가 10인 'abcabcacab'라고 했을때,

최종 failure function은 아래와 같은 배열의 형태를 띈다.

개념적으로는 failure function이라고하기 때문에 function인가? 싶을수도 있지만,

코드로 보자면 그냥 인덱스값을 가진 배열형의 변수다.

그리고 이 배열형의 변수 failure는, 찾고자 하는 문자열(keyword)이 반복하는 패턴을 기록해둔다.

 

즉 찾고자 하는 keyword가, 내부적으로 어떠한 '패턴'을 가지고 있다면

keyword를 찾기위해 전체 문자열인 origin과 0번 인덱스부터 비교해 나갈때,

서로 다르더라도 다시 처음부터 반복할 필요가 없게 만드는 것이다.

왜냐면 패턴만큼, 비교시의 인덱스를 건너뛰면되니까.

 

그럼 이제 failure라는 배열의 값들을 채우는 방법을 알아보자.

이를 채우는 개념은 아래와 같다.

 

1. 길이는 keyword와 동일
2. failure[0]의 값은 -1로 초기화한다.
3. 이후, 반복문을 통해 keyword배열을 순회하는데, 이때 중점은 현재 인덱스의 failure 값이 아니라,

   한 칸 앞의 failure 인덱스의 값보다 +1한 keyword의 '값'을 봐야한다는 것이다.

   왜냐면 이건 keyword의 '패턴'을 파악하기위한 것이니까. 아래 예시를 보자.

 

3-1. 만약 idx가 1이라면...failure[0]의 값인 -1보다 +1한 keyword[0]이 가지는 값인 'a'와,

      현재 idx의 keyword[1]의 값인 'b'를 비교한다.

      이 경우엔, 당연히 'a'와 'b'는 다르므로, failure[1]의 값은 -1로 채워지게 된다.

idx가 1일 때

3-2. 만약 idx가 3이라면...failure[2]가 가지는 -1보다 +1한 keyword[0]이 가지는 값인 'a'와,

      현재 idx의 keyword[3]의 값인 'a'를 비교한다.

      이때 keyword[0]과 keyword[3]은 둘다 'a'이므로,

      failure[3]에는 failure[2]의 값에 +1한 0이 채워진다.

idx가 3일 때

3-3. 만약 idx가 4이라면...failure[3]가 가지는 0보다 +1한 keyword[1]이 가지는 값인 'b'와,

      현재 idx의 keyword[4]의 값인 'b'를 비교한다.

      이때 keyword[1]과 keyword[4]은 둘다 'b'이므로,

      failure[4]에는 failure[3]의 값에 +1한 1이 채워진다.

idx가 4일 때

3-4. 만약 idx가 7이라면...failure[6]이 가지는 3보다 +1한 keyword[4]이 가지는 값인 'b'와,

      현재 idx의 keyword[7]의 값인 'c'를 비교하는데...

      이때 keyword[4]과 keyword[7]은 서로 다른 값이기 때문에, failure[7]은 다시 -1로 채워진다.

idx가 7일 때

4. 이렇게 반복된 후, 최종 failure는 아래와 같은 구성을 가지게 된다.

 

2. failure 배열을 활용해서 keyword 찾기

이제 origin과 keyword를 첫 번째 인덱스부터 비교하기 시작할텐데,

여기서 달라지는 점은 바로, 비교하는 두 값이 다를 때 failure 배열을 활용한다는 것이다.

 

현재 origin 은 'aabcacabcabcacab'이고 찾으려는 패턴은 keyword 'abcabcacab'이다.

이제, 두 문자열의 첫 인덱스부터 비교를 시작하는데,

빨간 색 선이 비교된 대상이다. 

이와 같이, keyword와 origin이 달라졌을 경우에

우리가 이미 만들어놓은 failure 배열을 활용해주는 것이다.

keyword의 m번째 인덱스값 1에서 keyword와 origin의 값이 다르다.

현재 m의 값이 1이므로 한 칸 앞의 failure[0]번 값을 보자.

failure[0]번의 값은 -1이므로, 여기에 1을 더한 값 0이 m의 값이 된다.

즉, m은 다시 0이되고 n은 여전히 1인채로, 한 칸씩 비교를 계속 해나간다.

파란색 선이 비교된 대상이다

그렇게 비교를 해나가다보면 m은 4, n은 5일 때 서로 값이 다르게 되는데

위에서 설명한 것과 같이 m이 4일 때 달라졌으므로

한 칸 앞의 failure[3]번 값을 보면 0이라는 걸 알 수 있고.

0에 1을 더한 '1'이라는 값이 m의 값이되어,

m은 1, n은 5인 상태로 keyword[1]과 origin[5]부터 다시 한 칸씩 비교하면 된다.

녹샌선을 보자

하지만 keyword[1]과 origin[5]는 서로 다른 값이고,

우리는 다시 m이 1이기때문에, 한 칸 앞의 failure[0]값을 봐야한다.

failure[0]은 -1의 값을 가지기때문에 다시 +1해서 0이 나오고

m은 0, n은 여전히 5인채로 keyword[0]과 origin[5]를 비교하면 되는데

주홍색 선을 보자

또 keyword[0]과 origin[5]는 다르다.

자, 이 시점에서 m은 0이고, 그보다 한 칸 앞서려면 failure[-1]이어야 하는데,

failure 배열에 이 값은 존재하지 않기때문에 이때는 n의 값을 1늘려서 비교를 다시 시작한다.

즉, n이 6으로 늘어나면서 keyword[0]과 origin[6]부터 한 칸씩 비교를 하는 것이다.

보라색 선을 보자

그렇게 한 칸씩 이동을 하게되면, 드디어 최종 패턴을 알 수 있게되었고

위 예시를 기준으로 보자면 m이 9인 상태로 패턴을 찾아내게되며,

찾고자했던 origin 문자열에서의 keyword 문자열의 위치값은

최종 n 값에서 keyword의 길이값을 뺀 6이 된다.

 

아래 코드는, 내가 정리한 Javascript KMP funciton 이다.

let kmp = function(origin, keyword){
      
      let oDump = origin.split('');
      let kDump = keyword.split('');
      let oLength = origin.length;
      let kLength = keyword.length;
      
      let failure = [];
      failure.length = kDump.length;
      failure.fill(-1);
      
      // failure 배열 세팅
      for(let i = 1; i < kLength; i++){
          let idx = (1 + failure[i-1]);
          if(kDump[i] === kDump[idx]){
              failure[i] = idx;
          } else{
              failure[i] = -1
          }
      }
      
      // 비교 시작
      let n = 0, m = 0;
      while(m < kLength && n < oLength){
          if(oDump[n] === kDump[m]){
              n++; m++;
          } else if(m === 0){
              n++;
          } else{
              m = 1 + failure[m-1]
          }
      }
      
      return m === kLength? (n - kLength) : -1
      
  }