[문자열 알고리즘] KMP 알고리즘

KMP 알고리즘이란?

위키백과에 따르면 커누스(Knuth),모리스(Morris),프랫(Pratt) 이 발견한 문자열 일치 문제에 대해 패턴정보를 활용하여 검색시간을 단축하는 방식 이라고 정의 되어 있습니다.

 

이러한 문제는 다음과 같은 경우에 빠른 시간에 문자열을 검색하기 위한 알고리즘인데요.

위와 같이 네이버에서 원당컴퓨터학원을 찾기 하면 원당컴퓨터학원이라는 글자에 표시가 되는 것을 조금 더 빠르게 해결하기 위한 패턴입니다.

 

KMP 알고리즘을 이해 하기 전에 먼저 브루트포스법 이라고 하는 알고리즘을 살펴 보겠습니다.

만약 문자열 S="ABCDABCDABBABCDABCDWZ" 가 있고

찾을 문자열 P="ABCDABCWZ" 라는 문자열이 있다면 

우리가 알고 있는 알고리즘은 다음과 같습니다.

ABCDABCDABBABCDABCDWZ 길이 s

ABCDABCWZ 길이 m

위와 같은 경우 B와 C 의 위치값이 틀리기 때문에 그 다음 위치와 비교하게 됩니다.

ABCDABCDABBABCDABCDWZ

  ABCDABCWZ

다시 B와 A 값이 틀리기 때문에 다음 위치로 이동합니다.

ABCDABCDABBABCDABCDWZ

    ABCDABCWZ

이렇게 한번씩 이동하면서 비교 하는 알고리즘이 브루트포스법이라고 불리우는 알고리즘으로 이중 for문을 사용하면 간단하게 처리 할 수 있습니다.

단점은 s * m 만큼의 시간이 걸린다는 것입니다.

이러한 검색 시간을 단축 시키기 위한 목적으로 만들어진 알고리즘이 바로 KMP 알고리즘입니다.

 

동작 원리는 다음과 같습니다.

ABCDABCDABBABCDABCDWZ

ABCDABCWZ

처음 D와 W 의 위치에서 불일치 하는 경우 브루트포스법과 같이 다음위치와 비교 하지 않고

ABCDABCDABBABCDABCDWZ

       ABCDABCDWZ

위와 같이 앞의 4칸을 건너 뛰어 비교하는 방식입니다.

 

이렇게 하기 위해서는 패턴을 만들어 두고 패턴만큼 이동하여 비교하면 되는데요.

다음과 같이 패턴을 만들면 됩니다.

0123456789

ABCDABCWZ

000012300

만약 빨간색 위치 W 위치에서 맞지 않는다면 바로 앞의 C의 위치인 3번째 위치인 D와 맞는지 비교 할 수 있도록 매칭에 실패했을때 돌아갈 상태를 준비해 두는 것입니다.

 

그렇다면 이러한 패턴을 만드는 방법은 어떻게 되는지 확인해 보겠습니다.

ABCDA

00001

A가 0번 위치와 동일합니다. 따라서 다음에 나오는 문자는 1번위치와 비교하면 됩니다.

ABCDAB

000012  

B가 1번 위치와 동일합니다. 따라서 다음에 나오는 문자는 2번위치와 비교하면 됩니다.

이런 규칙으로 패턴을 만들면 되는데요.

패턴을 만드는 것을 코드로 구현을 해 보도록 하겠습니다.

 

KMP 알고리즘   int kindex[100]; void kmp(char p[]) {   int len = sizeof(p);   int j=0;   for(int i=1;i<len;i++)   {     while(j>0 && p[i] !=p[j]) j= kindex[j-1]; //이전 위치로 찾아 가자     //012345678912345678901    //AACAADAABAACAAC    //010120120123453    //마지막 C 위치는 2번째 C와 동일한 결과값을 갖는다.     if(p[i]==p[j]) kindex[i]=++j; //비교위치를 기록하자.   }   }

 

여기에서 while(j>0 && p[i] !=p[j]) j= kindex[j-1];

이 문장은 서로 틀린 경우 바로 0번째로 가지 않고 그 전의 위치를 찾아서 가는 이유는 패턴의 길이가 길어지는 경우 앞의것을 재활용하기 위함입니다 

주석 처리 된 마지막 C의 위치는 2번째 C의 위치와 동일한 값을 갖게 됩니다.

 

KMP 알고리즘은 문자열 검색 알고리즘으로 많이 이용되는 알고리즘으로 알아 두면 매우 유용하게 사용 될 수 있습니다.^^

 

오늘도 화이팅! 입니다.^^