Algorithms/알고리즘 개념

[알고개념] 6. KMP Algorithm

퐁키조아 2022. 3. 27. 11:59

1. 문자열 찾기 알고리즘의 개요

워드 프로세서에서 단어 찾기와 같은 검색은 저장되어 있는 문자열을 대상으로 검색어가 포함된 문자열을 찾는 것이다. 검색이 가능하기 위해서는 검색어를 저장되어 있는 문자열의 부분 문자열과 비교하는 알고리즘이 필요하다. 예를 들어 ‘우리글’이라는 검색어를 ‘한글:⏘우리나라에서⏘창제된⏘우리글’ 이라는 띄어쓰기(⏘)가 포함된 18글자의 대상 문자열에서 검색한다고 가정해 보자. 가장 간단히 떠올릴 수 있는 방법은 ‘우리글’이 3글자이므로 대상 문자열을 3글자씩 잘라 1글자 씩 비교하는 것이다. ‘한글:’, ‘글:⏘’, ‘:⏘우’ 등과 같이 16개의 비교 대상을 만들고 이를 검색어와 각각 비교하여 모두 같은지 확인한다. 하나의 비교 대상을 확인하기 위해서는 3글자를 각각 비교해야 하므로 총 16×3번 비교를 하게 될 것이다. 검색어 길이에 비해 대상 문자열이 짧거나 같은 경우는 없으므로 이 방법은 검색어와 비교해야 하는 대상 문자열의 길이가 길어 지거나 개수가 많아지면 비교 횟수가 늘어나 검색 시간이 늘어난다.

검색 시간을 줄이기 위한 다른 방법은 없을까? 검색어와 비교 대상을 1글자씩 비교하지 않고 3글자씩 한 번에 비교할 수 있다면 그만큼 비교 횟수가 줄어들게 되어 검색 시간이 줄어들 것이다. 이를 위해 각각의 문자열에 특정 값을 생성하는 함수를 설정할 수 있다. 앞의 예와 같이 검색어가 3글자이고 18글자의 대상 문자열이 제시된다면 비교 대상은 16개가 만들어진다. 하지만 각 비교 대상에서 문자열 비교는 1번의 해시값 비교로 줄어들기 때문에 전체 비교 횟수는 감소하게 된다. 물론 해시값을 생성하는 해시 함수의 연산이 추가되지만 추가 되는 연산 시간이 각 글자 단위의 비교에 필요한 연산 시간보다 짧다면 전체적인 검색 시간은 단축될 수 있다.

- 2022년 고3 3월 모의고사 - 

이틀 전에 시행한 고3 3월 모의고사에서 KMP 알고리즘을 다룬 지문이 나와서 매우 반가웠다. 1문단에서 다루는 내용은 일반적으로 KMP 알고리즘을 몰랐을 때 사용하는 문자열 비교 알고리즘을 다루는데, 이 경우 시간 복잡도는 $O(NM)$ 이 된다. 그런데 2문단에서 언급하듯이 각 문자열에 특정 값을 부여하는 KMP 알고리즘을 사용하면 시간 복잡도가 $O(N+M)$으로 감소하여 훨씬 빠르게 검색을 할 수 있다. 이때 모의고사에서 각각의 문자열에 부여하는 특정 값은 해시 값이라고 설명하였지만, 실제 KMP에서는 실패 함수라는 개념을 사용한다.

이제 KMP 알고리즘을 알아보기 위해 문자열 S에서 문자열 W를 검색하는 상황을 생각해보자.

 

2. 실패 함수

먼저 W에 실패 함수값을 부여해보자. 실패 함수값 fail(x)란 W의 처음 (x+1) 글자 중 일치하는 접두사와 접미사 구간의 최대 길이를 의미한다. 이 값은 S와 W가 불일치했을 때 얼만큼 S가 이동해야하는지를 나타내는 값을 나타낸다. W = "ababaca" 일 때 fail 함수 값을 구해보자. 

  • W[0] = 0 -> a
  • W[1] = 0 -> ab
  • W[2] = 1 -> aba (a)
  • W[3] = 2 -> abab (ab)
  • W[4] = 3 -> ababa (aba)
  • W[5] = 0 -> ababac
  • W[6] = 1 -> ababaca (a)
int fail[MAX] = {0};
for (int i = 1, j = 0; i < M; i++){
    while(j > 0 && W[i] != W[j]) j = fail[j-1];
    if(W[i] == W[j]) fail[i] = ++j;
}

이 값을 구하는 과정도 S=W인 경우의 KMP 알고리즘을 이용하기 때문에 $O(M+M)$ 만큼 걸린다.

 

3. KMP 알고리즘

코드는 https://blog.naver.com/kks227/220917078260 참고

이제 https://www.acmicpc.net/problem/1786 이 문제를 풀면서 실패함수 값이 모두 부여된 W를 가지고 S에서 W를 찾는 과정을 알아보자. (아래에서 i는 S의 위치를 나타내고, j는 W의 위치를 나타내는 포인터이다. 편의상 S[i]를 s, W[j]를 w로 표시하겠다.) 

  1. i와 j가 모두 0에서 시작한다. i가 S의 끝까지 올 때까지 아래 과정을 반복한다.
  2. s와 w가 다르고 j가 0이면 i를 증가시키면서 W의 첫 글자와 같아질 때까지 옮긴다.
  3. s와 w가 처음으로 같아질 경우 j를 증가시키면서 W의 모든 글자가 같은지 확인한다. 만약 모든 글자가 같으면 result에 일치하는 위치를 저장하고, 찾지 못한 것처럼 j를 이동시키면 된다.
  4. j가 0이 아닐 때 s와 w가 다르면 실패함수 값을 이용하여 j를 이동시킨다. 예를 들어 위의 W 예시에서 j가 5일 때 값이 달랐다면 fail[5-1] 값인 3으로 j를 이동시킨다. 이제 다시 i를 증가시키면서 s와 w가 일치하는 경우를 찾아내면 된다.
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1000000;

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    string W, S;
    int M, N;

    getline(cin, S);
    getline(cin, W);
    N = S.size();
    M = W.size();

    // 실패 함수
    vector<int> fail(MAX, 0);

    for (int i = 1, j = 0; i < M; i++) {
        while (j > 0 && W[i] != W[j]) j = fail[j - 1];
        if (W[i] == W[j]) fail[i] = ++j;
    }

    // S, W의 일치하는 지점을 result에 모음
    vector<int> result;
    for (int i = 0, j = 0; i < N; i++) {
        // 현재 글자가 불일치하면 fail 값을 계속 따라감
        while (j > 0 && S[i] != W[j]) j = fail[j - 1];
        // 현재 글자가 일치
        if (S[i] == W[j]) {
            // W를 S[i:i+M-1]에서 찾음
            if (j == M - 1) {
                // i=0부터 시작한다면 i-M+1. 문제 조건에 따라 1을 더함
                result.push_back(i - M + 2);
                // 찾지 못한 것처럼 j를 이동시키면 됨
                j = fail[j];
            }
            else j++;
        }
    }

    // 결과 출력
    cout << result.size() << "\n";
    for (int i : result)
        cout << i << " ";
}
저작자표시