KMP 알고리즘

알고리즘/자료구조 2015. 2. 24. 18:38 Posted by 아는 개발자

예전에 KMP는 왜 KMP인가라는 문제를 보고 KMP이거 뭐지 장난하는건가 싶었는데;

문자열에 관한 알고리즘인걸 책을 보고 깨달았다.. 이렇게 심오하고 환상적인 알고리즘이 있었다니 ㄷㄷ


KMP알고리즘은 어떤 문자에서 특정 문자열이 존재하는지 확인하는 방법이다.

예를 들어 길이가 N인 문자열에서 M이라는 문자열이 있는지 없는지 확인하고 싶으면

N의 모든 위치에서 M의 시작문자와 비교해보는 방법이 있다. 이 방법은 O(MN)이 든다.


하지만 KMP알고리즘은 모두 비교하지 않고 접두사 접미사의 개념을 활용해서 푼다.


예를들어


abcabce -> 문자열 M

abcabcabcd -> 문자열 N


위의 M과 N을 비교했더니 abcabcabc까지는 같고 뒤에부터 달랐다.

그런데 다음 비교를 N의 두번째 문자열 부터 시작 하지 말고

abcabcabc의 접미사와 접두사가 같은 부분은 잘라서 하자는 것이다.

여기서 접두사 접미사가 같은 부분은 abc이다 따라서 N의 네번째 문자부터 탐색을 시작하면 효율적이다.


abcabcabcd

    abcabce

굵은a 부터 시작하라는것 왜냐면 앞에 있는 것들은 같은걸 아니까 따로 자료 구조를 만들어서 정리했으므로


문자열 N에 대하여 는 다음과 같은 자료 구조를 만들어야 한다


longestprefixsuffix[length];


length는 처음부터 length까지의 문자열 길이를 말하고

그 길이 까지 접미사와 접두사가 같은 부분의 최대 길이를 말한다.


구현은 다음과 같다.


#include<iostream>

#include<string>


using namespace std;



int p[1000];

int main()

{

string s;

cin>>s;


int begin=1, matched=0;


while(begin + matched < s.length())

{

if(s[begin + matched] == s[matched])

{

matched++;

p[begin + matched - 1] = matched;

}

else

{

if(matched == 0)

begin++;

else

{

begin += matched - p[matched-1];

matched = p[matched-1];

}

}

}


return 0;


}


접미사, 접두사 라는 개념을 사용하는건 이해가 가는데

이거를 깔끔하게 만드는 과정은 이해하기 어렵다.

'알고리즘 > 자료구조' 카테고리의 다른 글

오일러회로  (0) 2015.02.27
트라이  (0) 2015.02.27
트립(Treap)  (0) 2015.02.25
접미사배열  (0) 2015.02.24
KMP 알고리즘  (0) 2015.02.24
BIT(Binary Indexed Tree)  (0) 2015.02.21