[KMP] 카누스 모리스 프렛 알고리즘 (feat.cpp)

 

목차

• K.M.P 알고리즘 이란?
• 접두사, 접미사
• 구현
• 전체 코드
• 테스트 코드

 

K.M.P 알고리즘 이란?

 

m이라는 문자열 안에 n라는 문자열이 포함되는지 알고 싶은 경우 제일 먼저 생각나는 방법으로는

완전 탐색(Brute Force) 알고리즘이 먼저 생각날 것입니다.

완전 탐색은 간단한 구현만으로도 정확하게 문자열을 찾아낼 수 있지만 길이가 길어질수록 시간이 오래 걸립니다.

m 문자열 길이에 n 문자열 길이만큼 비교하게 되니 시간 복잡도는 O(mn)이나 나옵니다.

 

 

KMP 알고리즘은 저런 비교 결과들을 활용 하여 빠르게 문자열의 어느 INDEX 부터 시작할지를 결정합니다. 

아래 표를 보시면 첫 매칭에서 A B C A 까지는 맞지만 나머지가 틀려서 찾지못한 결과입니다.

 

INDEX	0	1	2	3	4	5	6	7	8
M	A	B	C	A	A	B	C	A	B
N	A	B	C	A	B

 

만약 완전 탐색으로 탐색을 진행했다면,  아래쳐럼 INDEX 1로 이동하여 비교를 진행할것입니다.

 

INDEX	0	1	2	3	4	5	6	7	8
M	A	B	C	A	A	B	C	A	B
N		A	B	C	A	B

 

하지만 KMP은 위에 A B C A 까지 맞은것을 이용하여 A (접두사, 접미사 일치) 한 곳부터 시작을 합니다.

 

INDEX	0	1	2	3	4	5	6	7	8
M	A	B	C	A	A	B	C	A	B
N				A	B	C	A	B

 

접두사, 접미사

 

정보를 활용할 수 있는 방법으로는 접두사 (PREFIX)와 접미사 (SUBFIX)가 같은 지점을 찾습니다.

 

ABCAB	접두사	접미사
	A	B
	AB	AB
	ABC	CAB
	ABCA	BCAB
	ABCAB	ABCAB

 

맨 아래 ABCAB는 정보를 찾은 결과이니 제외하고 접두사와 접미사가 같은 부분을 찾아보면  AB 가 있습니다.

이 정보를 가지고 생각해봅시다.

만약에 비교중에 접미사 부분에 포함된 부분이 일치하지만 나머지가 틀렸다면 시작 위치를 접미사로 옮겨도 되지 않을까요?

접미사와 접두사가 같다는 뜻은 시작 위치 값 = 끝나는 위치 값 같다 라는 말입니다.

 

구현

 

1.  n(찾을 문자열)에 대하여 접두사와 접미사가 같은 부분을 찾습니다.(PI 테이블 생성)

 

begin : 접미사 시작 부분

matched : 접두사 시작 부분

 

vector<int> get_pi(const string n){
    const int n_size = n.size();
    int begin = 1, matched = 0;
    
    vector<int> pi(n_size, 0);
    
    while(begin + matched < n_size){
        if(n[begin + matched] == n[matched]){
            ++matched;
            pi[begin + matched - 1] = matched;    
        }else{
            if(matched == 0){
                ++begin;
            }else{
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}

 

 

2. 문자열을 비교하고 만약 매칭이 되지 않을 시 PI테이블을 보고 시작할 위치를 정합니다.

 

ret : 찾는 패턴의 시작 위치들을 담고 있는 변수

 

vector<int> search_to_pettern(const string m, const string n){
    vector<int> ret;
    
    const int m_size = m.size();
    const int n_size = n.size();
    
    const vector<int> pi = get_pi(n);
    
    int begin = 0, matched = 0;
    
    while(begin + matched < m_size){
        if(matched < n_size && m[begin + matched] == n[matched]){
            ++matched;
            if(matched == n_size)
                ret.push_back(begin);
        }else{
            if(matched == 0)
                ++begin;
            else{
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return ret;
}

 

전체 코드

 

#include <iostream>
#include <vector>


using namespace std;

vector<int> get_pi(const string n){
    const int n_size = n.size();
    int begin = 1, matched = 0;
    
    vector<int> pi(n_size, 0);
    
    while(begin + matched < n_size){
        if(n[begin + matched] == n[matched]){
            ++matched;
            pi[begin + matched - 1] = matched;    
        }else{
            if(matched == 0){
                ++begin;
            }else{
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return pi;
}

vector<int> search_to_pettern(const string m, const string n){
    vector<int> ret;
    
    const int m_size = m.size();
    const int n_size = n.size();
    
    const vector<int> pi = get_pi(n);
    
    int begin = 0, matched = 0;
    
    while(begin + matched < m_size){
        if(matched < n_size && m[begin + matched] == n[matched]){
            ++matched;
            if(matched == n_size)
                ret.push_back(begin);
        }else{
            if(matched == 0)
                ++begin;
            else{
                begin += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    return ret;
}

 

테스트 코드 (필요하신 분만(

 

int main(){
    const string m = "aabaabacabaaaabaabac";
    const string n = "aabaabac";

    

    const vector<int> ret = search_to_pettern(m, n);

    for(auto & num : ret){
        cout << num << endl;
    }

    return 0;
}