[알고리즘] 문자열 탐색 알고리즘 KMP 그리고 활용 ❗️

문자열 탐색 중에서 가장 빠르다고 알려져있는 KMP 알고리즘에 대해서 정리해보겠다.

KMP 알고리즘은 백준 사이트에서 최소 골드 2 등급을 받는 문제들로 난이도가 있는 편이다.

하지만, 한 번 정리하고 사용해보고 나면 그렇게 어렵게 느껴지지는 않아서, 해당 내용 정리해보려고 한다.

이중 배열로 문자열 탐색하기

일단, KMP 알고리즘을 사용하지 않고 문자열을 탐색해 보자.

BADABCABDABCABCABDAB 라는 문자열 속에서 'ABCABDAB'라는 문자열을 찾으려면 어떻게 해야할까?

가장 쉽게 2중 for문을 통해 찾는 방법이 있다.

이때 찾을 문자열의 길이가 M, 대상 문자열의 길이가 N일 때의 시간 복잡도는 O(N*M)이 될 것이다.

for(int i=0; i<M-N+1; i++){
    bool flag = true;
    for(int j=0; j<N; j++){
        if(str[i+j] != A[j]){
            flag = false;
            break;
        }
    }
}

그러나 보통 KMP를 사용하는 문제들은 M의 길이 50만, N의 길이가 100만 이런식으로 문제가 나온다..
즉 이중 배열로 풀면 시간 초과로 망한다 ㅎㅎ
여기서 시간을 더 줄이는 방법을 어떻게 생각할 수 있을까?

처음으로 돌아가서 다시 비교하지 말자

실패할 경우 다시 처음으로 돌아가기 보다,

실패하더라도 문자열의 특성을 생각하여 일부 맞은 부분의 다음부분부터 비교를 시작하는 것이다.

따라서 찾을 문자열에 대한 fail 배열에 대해서 구해 본다.

fail 배열의 해당 문자열의 처음부터 비교하여 연속적으로 일치하는 부분 문자열의 최대 길이라고 할 수 있다.

ABCABDAB 같은 경우 "AB"라는 부분 문자열이 반복적으로 나타나는 특성을 생각해 보았을 보았을 때,

인데스 0~4 (ABCAB) 까지는 일치하고, 인덱스 5인 D에서 불일치할 경우,

다시 처음 인덱스인 A부터 비교하는 것이 아니라, 이미 AB까지는 일치하기 때문에,

인덱스 2번인 C와 일치하는 지 비교를 하는 것이 좋을 것이다.

fail 배열 구현하기

따라서 해당 인덱스 값을 넣어놓은 fail 배열은 다음과 같은 코드를 사용하여 구할 수 있다.

int j = 0;

for(int i=1; i<A.length(); i++){
  while(j>0 && A[i]!=A[j]){
      j = fail[j-1];
  }
  if(S[i]==S[j]){
      fail[i] = ++j;
  }
}

fail 배열을 만드는 데에는 O(N)의 시간복잡도를 가지는 것을 알 수 있다.

그렇다면 탐색을 하는데, O(M)만에 할 수 있기 때문에 총 O(N+M)의 시간복잡도를 가지게 된다.

탐색 코드 구현하기

해당 코드는 탐색을 하는 코드이다.

int j = 0;
for(int i=0; i<B.length(); i++){

  while(A[j] != B[i] && j > 0){
      j = kmp[j-1];
  }
  if(A[j] == B[i]) j++;

  if(j == A.length()){
      cout << "FIND\n";
    break;
  }
}

🦔 풀어볼 만한 백준 문제들

16916번 부분 문자열

1786번 찾기

16900번 이름 정하기