KMP 문자열 탐색 알고리즘이 동작하는 구체적인 원리

KMP 문자열 탐색 알고리즘이 동작하는 구체적인 원리

웹 브라우저 상에서 찾고싶은 단어를 Ctrl + F 로 순식간에 찾을 수 있다

웹 브라우저 상에서, 현재 페이지에 포함되어 있는 특정 단어를 찾고싶다면 Ctrl + F 로 정말 순식간에 원하는 단어를 모두 찾을 수 있습니다.

이처럼 글 안에서 단어를 빠르게 찾거나, 문자열을 전처리하여 우리가 원하는 정보를 추출하는 알고리즘은 여러 분야에서 매우 중요하게 다루어 집니다.

인간이 정보를 교환하고 기록하는 방식이 문자 이니, 문자열 안에 대부분의 정보가 담겨있기 때문이죠.

특히나 매일 수천만명이 사용하는 네이버의 검색엔진 과 같은 경우 사용자들이 작성하는 수십만개의 블로그 포스트나 쇼핑 후기 등을 알맞게 전처리하여 검색엔진을 통해 수 초 안에 알맞는 정보를 빠르게 검색 할 수 있어야 하겠죠.

이처럼 문자열 탐색 알고리즘 은 인터넷 탄생한 이후 더 빠른 알고리즘이 지속적으로 요구되어 왔으며 이에 맞게 발전해왔습니다.

대표적인 문자열 안에서 단어를 찾는 문자열 탐색 알고리즘으로 라빈-카프, 보이어-무어, KMP 알고리즘 등 이 있으며 문자열 안에서 여러개의 단어를 동시에 찾는 방법으로 아호-코라식 알고리즘이, 다양한 문자열 처리 문제에서 유용하게 적용할 수 있는 문자열 처리 분야의 ‘맥가이버 칼’ 인 접미사 배열을 빠르게 생성하는 맨버-마이어스의 알고리즘 등이 개발되어 왔습니다.

오늘은 문자열 탐색 알고리즘에서 가장 중요한 아이디어를 담고있는 KMP 문자열 탐색 알고리즘 이 작동하는 원리에 대해 구체적으로 알아보겠습니다.

문자열 탐색, 무식하게 해보자!

문자열 안에서 특정 단어를 검색하는 가장 간단한 방법, 전부 비교하기

가장 간단하고 쉽게 생각할 수 있는 문자열 탐색 방법은 바로 원본 문자열과 우리가 찾고싶은 탐색 문자열을 모든 문자에 대해서 하나하나 비교해보는 방법입니다.

위처럼 원본 문자열의 맨 앞 문자부터 탐색을 시작하여, 탐색 문자열과 다른 문자가 발견된다면 두번째 문자부터 다시 비교하는 과정을 계속 반복하는 아주 간단한 방법이죠.

위처럼 문자열이 일치하지 않는다면, 두번째, 세번째 문자부터 비교하는 과정을 반복합니다.

문자열이 일치한 경우

위처럼 탐색 문자열을 원본 문자열의 모든 부분에 대해서 비교하는 방식은 매우 간단하지만 그만큼 매우 느립니다.

구체적으로 어떤 상황에서 위의 알고리즘이 느려지는지 살펴보겠습니다.

간단한 문자열 탐색 알고리즘이 매우 느려지는 경우

위처럼 탐색 문자열이 AAAAE 이고 원본 문자열이 AAA... 처럼 A 가 계속 반복된다면 그다지 똑똑하지 못한 우리의 알고리즘은 탐색 문자열을 매번 끝까지 탐색해야 하므로 느려질 수 밖에 없습니다.

이때의 시간 복잡도는 원본 문자열의 길이가 N, 탐색 문자열의 길이가 M 일떄 O(NM) 이라고 할 수 있습니다.

O(NM) 의 시간 복잡도, 과연 괜찮을까요?

일반적으로 인터넷에 작성되는 글 들은 매우 많은 문자를 포함하고 있습니다.

우리가 매일 보는 네이버의 메인 페이지 에도 약 3천 자 의 문자가 포함되어 있네요.

이때 O(NM) 의 시간복잡도 로는 우리가 탐색하고자 하는 단어가 10글자 만 되도, 네이버 메인 페이지를 10번 반복해서 읽어야 우리가 원하는 단어를 찾을수 있는 것과 같습니다.

끔찍하게 느리죠! 사람은 글을 한번 만 읽고도 원하는 단어를 쏙쏙 찾을 수 있는데 우리의 단순한 알고리즘은 글을 10번이나 반복해서 읽어야 그제서야 단어를 찾을수 있는것 이죠.

또한 탐색하고자 하는 문자열의 길이에 비례에서 탐색 시간도 늘어나는 치명적인 문제점도 발생합니다.

마치 사람처럼 글을 한번만 읽고 원하는 단어를 탐색하는것은 우리의 알고리즘에게는 불가능 한 일 일까요?

문자열 탐색을 보다 빠르게 하기 위한 대표적인 문자열 탐색 알고리즘이 오늘 알아볼 KMP 알고리즘 입니다.

KMP 알고리즘 을 사용하면 무려 O(N+M) 의 시간복잡도 만으로 문자열을 탐색할 수 있습니다! 사람처럼 문자열을 거의 한번만 읽고도 원하는 단어를 찾아낼 수 있는것이죠.

그렇다면 KMP 알고리즘 이 어떤 원리로 보다 빠르게 문자열을 탐색할 수 있는지 알아보겠습니다.

KMP 알고리즘을 들어가기 전에, 접두사와 접미사만 알아볼게요

KMP 알고리즘에서 메인 아이디어로 사용되는 접두사와 접미사의 정의

KMP 알고리즘을 이해하려면 접두사와 접미사의 개념을 짚고 넘어가야 합니다. 매우 쉽습니다!

KMP 알고리즘에서 정의하는 접두사와 접미사 란, 문자열에서 맨앞과 맨 뒤에서 같은 문자열이 나오는 경우를 말합니다.

위의 그림에서 ABCAB 에서의 접두사와 접미사는 문자열 앞뒤에서 동일하게 찾을 수 있는 AB 가 됩니다.

접두사와 접미사의 정의를 알아보았으니, 바로 KMP 알고리즘의 아이디어에 대해 알아보겠습니다.

KMP 알고리즘의 아이디어

KMP 알고리즘의 아이디어

앞서 우리가 생각해 냈던 간단한 알고리즘은, 탐색 문자열을 모든 원본 문자열의 위치에 대해서 문자 하나하나 비교해보는 방식이였습니다.

KMP 알고리즘의 개발자 Knuth, Morris, Pratt 는 우리가 생각해 냈던 간단한 알고리즘에서 문자 하나하나 비교하지 말고 일정 부분을 건너뛸 수 없을까? 라는 아이디어를 떠올렸습니다.

문자열이 불일치 하는 경우, 일정 부분을 건너 뛸 수 없을까?

문자열을 조금더 이해하기 쉽게 맨 앞 부터 마지막 문자까지 색을 입혀보았습니다.

KMP 알고리즘의 가장 중요한 아이디어는 문자열이 불일치 할 때 탐색을 시작했던 위치의 다음 문자 부터가 아닌, 우리가 앞서 탐색했던 정보를 이용하여 몇칸 정도는 건너 뛴 후 탐색할 수 있지 않을까? 부터 시작합니다.

문자열 탐색을 건너 뛸 수 있다면, 건너 뛴 후의 부분이 동일해야 한다.

위의 사진이 KMP 알고리즘의 메인 아이디어 입니다.

우선 너무 복잡하게 생각하지 말고 문자열이 불일치 할 때 탐색을 시작했던 위치의 다음 문자 부터가 아닌 일정 부분을 건너 뛸 수 있다고 가정을 해봅시다.

만약 문자열 탐색을 건너 뛸 수 있다면 어떤 전제조건이 꼭 성립해야 할 까요?

건너 뛴 후의 탐색 문자열의 앞 부분과 원본 문자열의 뒷 부분이 일치해야 한다 가 전제조건으로 성립해야 합니다.

위의 그림에서 이 전제조건이 성립해야 하는 이유를 표현하고 있는데요.

문자열 탐색을 일정 부분 건너 뛴후 원본 문자열과 탐색 문자열을 비교한다는 것 의 의미는 건너 뛴 후 부터는 다시 원본 문자열과 탐색 문자열이 일치해야한다는 의미입니다!

건너 뛴 후의 원본 문자열과 탐색 문자열이 일치해야 그 이후로 다시 탐색을 진행 할 테니까요.

반대로 일정부분 건너 뛴 후 원본 문자열과 탐색 문자열이 일치하지 않는다면, 건너 뛰는 의미가 없죠! 건너뛰어봐야 문자열이 일치하지 않으니까요.

여기서 얻을 수 있는 결론은 탐색 문자열의 앞 부분과 원본 문자열의 뒷부분이 동일한 부분 까지는 문자열 탐색을 건너뛸 수 있다는 사실입니다!

탐색 문자열의 접두사와 접미사를 미리 알고있다면, 얼마큼 건너뛸 수 있을지를 계산할 수 있다

따라서 위의 사진처럼 탐색 문자열의 접두사와 접미사를 미리 알고있다면 원본 문자열과 탐색 문자열에서 불일치가 발생할 때 얼마큼 건너뛸 수 있을지를 계산해낼 수 있습니다. 정말 아름다운 아이디어죠!

이는 앞서 우리가 생각해냈던 모든 부분을 비교하는 알고리즘 과 비교했을때 더 똑똑하게 작동합니다.

굳이 불필요하게 탐색하는 부분을 건너 뛰어서 다음 탐색을 진행할 수 있으니까요.

KMP 알고리즘에서 탐색 문자열의 접두사와 접미사를 미리 계산해야 하는 이유, 이제 이해되셨나요?

이제 왜 KMP 알고리즘에서 탐색 문자열의 접두사와 접미사의 길이를 미리 계산해 놓는지 이해가 되시나요?

탐색 문자열의 접두사와 접미사의 길이를 알아야, 그만큼 건너뛴 후에 탐색을 진행 할 수 있기 때문이죠!

탐색 문자열의 접두사와 접미사의 길이를 미리 계산해 놓을 수 있다면, 원본 문자열과 비교하면서 불일치가 발생하면 미리 계산해둔 접두사와 접미사의 길이를 불러온 후 그만큼 건너뛴 후 탐색을 진행하면 됩니다.

여기까지의 내용을 정리하자면 KMP 알고리즘의 아이디어는 다음과 같습니다.

탐색 문자열의 앞부분과 원본 문자열의 뒷부분이 동일한 부분 까지는 문자열 탐색을 건너 뛸 수 있다!

KMP 알고리즘의 아이디어와 왜 접두사와 접미사의 길이가 필요한 지 이해가 되셨나요?

이러한 아이디어와 이론에서 한발짝 더 나아가 소스코드로 어떻게 KMP 알고리즘이 구현되는지 살펴보겠습니다.

KMP 알고리즘의 구현

우선 우리가 처음 생각해냈던 모든 문자열의 부분을 비교하는 문자열 탐색 알고리즘 부터 구현해 보겠습니다.

vector<int> bruteForce(string& src, string& search){
    vector<int> ret;
    
    // 원본 문자열의 처음 부터 끝 까지 탐색
    for(int begin = 0; begin + search.size() <= src.size(); begin++){
        bool matched = true;
        
        // 탐색할 문자열과 원본 문자열을 비교
        for(int i = 0; i < search.size(); i++){
            // 불일치 발생
            if (src[begin + i] != search[i]){
                matched = false;
                break;
            }
        }
        // 탐색할 문자열과 원본문자열이 일치
        if (matched)
            ret.push_back(begin);
    }
    
    return ret;
}

간단한 알고리즘 답게, 탐색 문자열과 원본 문자열의 모든 부분을 2중 반복문으로 비교하는 것 을 볼 수 있습니다.

반면에 더 똑똑한 알고리즘인 KMP 알고리즘은 어떻게 구현할 수 있을까요?

vector<int> kmpSearch(string& src, string& search){
    int n = src.size(), m = search.size();
    vector<int> ret;
    // 탐색할 문자열의 접두사, 접미사 길이를 문자열의 처음부터 끝 까지 미리 계산
	vector<int> pi = getPartialMatch(search);    
	int begin = 0, matched = 0;
    
    while(begin <= n - m){
        // 탐색할 문자열과 원본 문자열에서 현재 위치의 문자가 동일한 경우
        if (matched < m && src[begin + matched] == search[matched]){
            ++matched;
            
            // 문자열이 모두 일치하는 경우
            if (matched == m)
                ret.push_back(begin);
        }
        else{
            // 일치하는 부분이 없는 경우, 다음 위치의 문자 부터 탐색
            if(matched == 0)
                ++begin;
            
            // 문자열이 불일치 하므로 접두사, 접미사 의 길이 만큼 건너 뜀!
            else{
                // 현재 불일치가 발생한 위치는 begin + matched
                // 여기서 접두, 접미사의 길이인 pi[matched - 1] 을 빼주면 다음 탐색 시작 위치
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    
    return ret;
}

getPartialMatch() 함수는 탐색 문자열의 접두, 접미사의 길이를 구해주는 함수입니다. 바로 뒤에서 직접 구현해 볼 예정이니 지금은 이해를 위해 잠시 넘어가주세요!

getPartialMatch() 함수는 탐색 문자열의 맨 처음 부터 첫 번째, 두 번째, … , 마지막 부분 까지에 대한 접두, 접미사의 길이를 미리 계산하여 반환합니다.

그 이후 만약 탐색을 진행 하다 탐색 문자열의 5번 째 문자 에서 불일치 가 발생했다면, pi[ 5 - 1] 처럼 5번째 문자 앞의 가장 긴 접두, 접미사의 길이를 받아온 후 그만큼 건너뛴 후 탐색을 다시 진행하면 되겠죠.

문자열 불일치가 발생했다면, 현재 탐색하고 있는 문자의 위치는 원본 문자열을 기준으로 begin + matched 가 됩니다.

따라서 begin 에다가 matched 를 더해준 뒤, pi[matched - 1] 를 빼주면 KMP 알고리즘의 아이디어 대로 접두, 접미사가 일치하는 다음 탐색 위치를 한번에 얻을 수 있게 됩니다.

그렇다면 탐색 문자열의 접두, 접미사의 길이는 어떻게 계산할 수 있을까요?

우리가 계산하고 싶은 탐색 문자열의 접두, 접미사 길이를 담은 배열 출처: 알고리즘 문제 해결 전략

우리가 구하고자 하는 탐색 문자열의 접두, 접미사 길이를 담은 배열은 구체적으로 위의 사진과 같습니다.

탐색 문자열의 접두, 접미사 길이를 계산하는 과정 출처: 알고리즘 문제 해결 전략

가장 간단하게 접두, 접미사의 길이를 담은 배열을 구하는 방법은 위처럼 맨 앞부터 모두 비교해보는 방법입니다.

직접 구현해보면 다음과 같습니다.

vector<int> getPartialMatchBruteForce(string& search){
    int m = search.size();
    vector<int> pi(m, 0);
    
    // 탐색 문자열의 처음부터 끝까지 모두 비교해 보면서 접두, 접미사의 길이를 계산한다
    for(int begin = 1; begin < m; begin++){
        for(int i = 0; begin + i < m; i++){
            if (search[begin + i] != begin[i])	break;
            pi[begin + i] = max(pi[begin + i], i + 1);
        }
    }
    
    return pi;
}

2중 반복문으로 탐색 문자열의 처음부터 끝까지를 모두 살펴보면 접두, 접미사의 길이를 계산해 낼 수 있습니다.

2중 반복문은 탐색 문자열의 길이가 길어지면 너무 느려질 것 같다구요? 정답입니다!

우리가 원하는건 탐색 문자열이 길어져도 빠르게 문자열 탐색을 진행하고 싶어서 KMP 알고리즘을 사용하는 것 인데, 탐색 문자열의 접두사와 접미사를 계산하는 과정에서 2중 반복문으로 O(N^2) 만큼의 시간을 소요하면 탐색 문자열의 길이가 길어질 수록 소요 시간도 늘어나겠죠.

탐색 문자열의 접두, 접미사 길이를 조금 더 빠르게 계산 해 낼 방법은 없을까요?

놀랍게도, KMP 알고리즘을 여기서도 동일하게 적용할 수 있습니다!

위의 과정을 잘 살펴보면 탐색문자열에 대해서 앞뒤로 탐색문자열 자신을 매칭시키는 과정이라는 것 을 알 수 있습니다.

따라서 문자열 매칭 과정 과 본질적으로 다르지 않습니다.

탐색 문자열의 접두, 접미사를 계산하는 과정에 KMP 알고리즘을 적용하면 다음과 같습니다.

vector<int> getPartialMatch(string& search){
    int m = search.size();
    vector<int> pi(m, 0);
    
    int begin = 1, matched = 0;
    
    while(begin + matched < m){
        // 탐색 문자열과 탐색 문자열 자신을 매칭시킴!
        if(search[begin + matched] == search[matched]){
            matched++;
            pi[begin + matched - 1] = matched;	// 매칭을 진행하면서, 접두 접미사 배열을 바로 갱신
        }
        else{
            if(matched == 0)
                begin++;
            else{
                // KMP 문자열 탐색 알고리즘 과 동일하게 불일치 발생 시
                // 매칭을 진행하면서 구했던 접두 접미사 길이 만큼 탐색을 건너뛸 수 있다
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    
    return pi;
}

여기까지 탐색 문자열의 접두, 접미사 길이 배열과 문자열 탐색 알고리즘을 가장 간단한 방법에서 부터 KMP 알고리즘 까지 단계별로 최적화 하면서 구현해보았습니다.

KMP 알고리즘의 구현 또한 중요하지만, 왜 접두 접미사가 문자열 탐색을 빠르게 하는 데 유용하게 사용되는 지 에 대한 아이디어의 이해가 가장 중요하다고 할 수 있습니다.

KMP 알고리즘의 시간 복잡도

KMP 알고리즘에서 접두, 접미사의 길이를 이용하여 탐색을 건너뛰는 아이디어를 이해하고 있다면 시간 복잡도는 소스코드만 분석해도 계산할 수 있습니다.

vector<int> kmpSearch(string& src, string& search){
    int n = src.size(), m = search.size();
    vector<int> ret;
	vector<int> pi = getPartialMatch(search);    
	int begin = 0, matched = 0;
    
    while(begin <= n - m){
        if (matched < m && src[begin + matched] == search[matched]){
            // 일치하는 경우 matched 가 1 증가
            ++matched;

            if (matched == m)
                ret.push_back(begin);
        }
        else{
            // 완전 불일치 하는 경우 begin 이 1 증가
            if(matched == 0)
                ++begin;
            
			// 접두 접미사가 존재하는 경우
            else{
                // begin 은 증가, matched 는 감소
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    
    return ret;
}

위의 소스코드를 기반으로 KMP 알고리즘의 최악의 상황을 한번 생각해 봅시다.

문자열 매칭이 항상 탐색 문자열의 마지막 문자 직전까지는 성공하고, 마지막 문자에 실패하는 경우가 최악의 상황이겠죠.

이때 시간 복잡도는 어떻게 될까요?

1. 우선 matched 가 탐색 문자열의 길이 - 1 만큼 증가합니다.

2. 그 후 문자열 불일치가 탐색 문자열의 마지막 문자에 발생하였으므로, matched = pi[matched - 1] 로 접두 접미사의 길이만큼 계속 감소하게 됩니다.

이때 접두 접미사의 길이는 항상 현재 탐색 문자열의 길이보다 1 이상 작으므로 최대 matched 회 만큼 감소하면 0이 됩니다.

예를들어, 탐색 문자열이 AAAAA 일때 접두, 접미사는 AAAA 입니다. 접두 접미사가 탐색문자열 자신 보다 항상 짧은걸 알 수 있죠.

위의 1, 2번 과정이 진행되면 begin 의 위치는 얼마큼 진행되었을까요?

begin += matched - pi[matched - 1] 가 반복되므로, 결국 begin 은 begin + matched 에 위치하게 됩니다.

따라서 KMP 알고리즘의 최악의 경우 1번 과정에서 matched 가 탐색 문자열의 길이-1 만큼 증가한 후 2번 과정에서 최대 matched 회 만큼 감소 한 결과 begin 이 begin + matched 만큼 이동하였다는 것 을 알 수 있습니다.

즉, begin 이 begin + matched 로 이동하는데 최악의 경우에도 과정1 + 과정 2 = matched * 2 회 만큼 소요된다는 것 이죠.

따라서 KMP 알고리즘의 시간 복잡도는 탐색하고자 하는 문자열의 길이에 비례하게 됩니다.

원본 문자열의 길이가 N, 탐색 문자열의 길이가 M 이라면 최종적인 시간 복잡도는 O(N + M) 이 되는것이죠.

시간 복잡도 O(N + M) 이 정말 놀라운점은, 이 이하로 더 빠른 알고리즘을 고안하기는 매우 어렵다는 것 이죠.

간단히 생각해봐도, 원본 문자열과 탐색할 문자열을 단 1번 씩 만 읽어도O(N + M) 의 시간복잡도가 소요됩니다.

따라서 O(N + M) 이하의 시간복잡도라면 원본 문자열과 탐색할 문자열 중 일부를 읽지 않아도 탐색이 가능하다는 소리겠죠! 이는 불가능에 가깝다는 것 을 쉽게 이해할 수 있습니다.

KMP 알고리즘의 시간 복잡도는 O(N+M) 이며, 이는 문자열을 한번만 읽고 탐색하는 것과 같은 시간 복잡도 이므로 이론상으로 가장 빠른 문자열 탐색 알고리즘이다.

결론

지금까지 가장 간단한 문자열 탐색 알고리즘 부터 시작해서 그 단점을 개선한 KMP 알고리즘이 작동하는 구체적인 원리와 소스코드를 통한 구현, 시간복잡도 까지 KMP 알고리즘의 거의 모든것 에 대해서 구체적으로 살펴보았습니다.

KMP 알고리즘의 원리를 이해하는 것 이 중요한 이유는, KMP 알고리즘에서 사용된 접두 접미사 아이디어가 문자열 처리에 관련된 다양한 알고리즘에 조금씩 녹아들어있기 때문입니다.

따라서 KMP 알고리즘을 이해하고 있다면, 문자열 처리에 관련된 다른 알고리즘을 이해하는데 많은 도움이 됩니다.

또한 문자열은 세상에 존재하는 가장 많은 데이터의 종류이며 인간이 정보를 기록하고 공유하는 방식이기 때문에 문자열 처리 알고리즘 또한 중요할 수 밖에 없습니다.

KMP 알고리즘은 이론상 최고의 성능을 뽐낸다는 점과 좋은 아이디어 덕분에 학부과정에서 배우기도 하고 최근에 코딩테스트에도 많이 출제되고 있습니다.

하지만 소스코드만 외우고 원리에 대한 이해가 없다면 무용지물 이겠죠!

이 글이 많은 도움이 되었길 바랍니다.

긴 글 읽어주셔서 감사합니다.

Reference

• 알고리즘 문제 해결전략 (종만북)