강의실/정보영재

KMP 알고리즘이란?

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


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

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


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

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

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

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

ABCDABCDABBABCDABCDABC 길이 s

ABCDABCWZ 길이 m

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

ABCDABCDABBABCDABCDABC

  ABCDABCWZ

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

ABCDABCDABBABCDABCDABC

    ABCDABCWZ

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

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

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


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

ABCDABCDABBABCDABCDABC

ABCDABCWZ

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

ABCDABCDABBABCDABCDABC

       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 알고리즘은 문자열 검색 알고리즘으로 많이 이용되는 알고리즘으로 알아 두면 매우 유용하게 사용 될 수 있습니다.^^


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





이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
6 0
  • 행복사냥이 2019.04.09 23:40 신고    

    헉! 오늘은 너무 전문적인 내용이라 잘 모르겠어요.ㅎ 항상 행복한 하루 보내세요.^^

  • 베짱이 2019.04.09 23:55 신고    

    알고리즘....
    코드가 난무해서 어렵게 느껴지네요. ㅋㅋ

  • 핑구야 날자 2019.04.10 06:45 신고    

    Kmp 알고리즘이군요 조금 어렵지만 덕분에 잘 알고 갑니다

  • 휴식같은 친구 2019.04.10 09:15 신고    

    kmp알고리즘에 대해서 배워가네요.
    즐거운 하루 되세요.

  • 공수래공수거 2019.04.10 09:20 신고    

    필요하신분들은 알아두면 좋을듯 합니다.^^

  • 버블프라이스 2019.04.10 17:44 신고    

    아, KMP 알고리즘 어렵지만 덕분에 알고 갑니다^^
    즐거운 수요일 되세요