KMP 알고리즘

문자열이 아닌 바이너리 모드에서 기존 STL의 문자열 탐색 라이브리는 정상 작동되지
않는다.

바이너리 속에서 특정 바이너리 패턴을 찾을 일이 있을때, 문자열 알고리즘 중에 KMP 알고리즘이 가장 효율적이다.

1.기본 개요

위 그림의 문자열 비교 처럼 문자열이 일치하지 않을때, 이미 비교한 부분의 정보를 가지고 불필요한 비교를 피하는것이 KMP알고리즘의 원리의 전부이다.

이 알고리즘을 적용하려면 패턴이 어디까지 일치하였을때, 얼마만큼 패턴을 스킵해야 할지 계산할 필요가 있다.

일치 텍스트와 패턴을 비교하지 않고 미리 패턴의 접두사와 접미사를 이용해 패턴의 접두 접미 일치표를 만들어놓고 실제 텍스트와 패턴 비교시 사용하는것이 접두 접미 일치표이다

패턴     ababaca

텍스트 bacbababaabacbab

아래의 코드를 첨부한다

#include 
#include 
#include "Kmp_Header.h"

KmpSearch::~KmpSearch()
{
 if (!m_pMatchTable)
  free(m_pMatchTable);
}
int KmpSearch::SearchKmp(Byte* text, Byte* pattern, int textLen, int patternLen)
{
 m_textLen = textLen;
 m_patternLen = patternLen;
 m_text = text;
 m_pattern = pattern;

 PrefixPI();
 Matching();
 return 1;
}
int KmpSearch::PrefixPI()
{
 m_pMatchTable = (int*)malloc(sizeof(int)*m_patternLen);

 int i = 1; //접미사 
 int j = 0; //접두사

 m_pMatchTable[0] = 0;

 while (i < m_patternLen)
 {
  if (m_text[i] == m_pattern[j])
  {
   m_pMatchTable[i] = j;
   i++;
   j++;
  }
  else if (j > 0)
  {
   j = m_pMatchTable[j - 1];
  }
  else
  {
   m_pMatchTable[i] = 0;
   i++;
  }

 }//while
 return 1;
}

int KmpSearch::Matching()
{
 int i = 0; //text index
 int j = 0; //pattern index
 while (i < m_textLen)
 {
  if (m_text[i] == m_pattern[j])
  {
   if (j + 1 == m_patternLen)
    return  i - j;
   i++;
   j++;
   
  }
  else if (j>0) //i는 고정 전 j값으로 비교 다르기 전까지 접두사 비교 일치
  {
   j = m_pMatchTable[j-1];
  }
  else
  {
   i++;
  }
   
 }
 return -1;
}

사용 방법

 PrefixPI((unsigned char*)pattern, _mbstrlen(pattern));
 int result = Matching((unsigned char*)text, _mbstrlen(text), (unsigned char*)pattern, _mbstrlen(pattern));

-참고 서적-

1. 다양한 예제로 배우는 알고리즘

(나라심하 카루만치 저 전계도, 전형일 역 인사이트 2014.02.22.)

http://book.naver.com/bookdb/book_detail.nhn?bid=7430898


2. Introduction to Algorithms.