7 -3장 KMP법

1. KMP법 알아보기 

 

- 중간 검사 결과를 효율적으로 사용하는 알고리즘

- 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘 

 

- 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구해서 

 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높임

 

ex) 텍스트 "ZABCABXACCADEF"에서 패턴 "ABCABD"를 검색하는 경우 

 

- 텍스트, 패턴의 첫 문자부터 순서대로 검사 

- 'Z'는 패턴에 없는 문자이므로 불일치 판단

 

- 패턴을 1칸 뒤로 이동

- 패턴의 마지막 문자는 'D'여서 텍스트의 'X'와 불일치 

- 텍스트의 AB와 패턴의 AB가 일치한다는 점 이용 

 -> 이 부분은 이미 검사를 마친부분이므로 텍스트 'X' 다음 문자부터 패턴의 'CABD'가 일치하는지만 검사 

 

- 'AB'가 겹치도록 패턴을 한 번에 (3칸) 이동시키고 3번째문자인 'C'부터 검사

 

- '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 "표"로 만듬

 

- 패턴의 1~4번째 문자에서  검사에 실패한 경우에는 패턴을 옮긴 다음 1번째 문자부터 다시 검사 

 

- 패턴의 5 번째 문자에서 검사에 실패한 경우에는 패턴을 옮긴 다음

  1번째 문자가 일치하므로 2번째 문자부터 다시 검사 

- 패턴의 6번째 문자에서 검사에 실패한 경우에는 3번째 문자부터 다시 검사 가능

 

< 표만들기>

 

- 표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아야 함 

- 패턴 안에서 중복되는 문자열 나열을 찾기 위해 패턴끼리 겹쳐놓음

 

1) 초록색 부분이 겹치지 않으므로 패턴을 옮긴 다음 앞쪽의 1번째 문자부터 검사를 다시 시작해야함

 표에서 2번째 문자(B)의 값을 0으로 함 

 2) 패턴을 1칸 뒤로 옮기고 문자가 일치하지 않으므로 표에서 3번째 문자 (C)의 값을 0으로 함

 

 3) 패턴을 1칸 뒤로 옮기면 "AB"가 일치 

 

 -패턴의 4번째 문자 'A'까지 일치한다면 아래에 위치한 패턴을 1칸 옮긴 다음 "A"를 건너뛰고 2번째 문자부터 검사 가능

 -패턴의 5번쨰 문자 'B'까지 일치한다면 아래에 위치한 패턴을 1칸 옮긴 다음 "B"를건너뛰고 3번째 문자부터 검사 가능

 

 

 4) 패턴을 2칸 뒤로 옮기면 문자가 일치하지 않음 

 

- KMP법을 사용해 문자열을 검색하는 함수 

//KMP법으로 문자열 검색  
#include <stdio.h> 

int kmp_match(const char txt[], const char pat[])
{
	int pt=1; //txt 커서  
	int pp=0; //pat 커서 
	int skip[1024]; //건너뛰기표 
	
	//표만들기  
	skip[pt] = 0;
	while(pat[pt] != '\0') {
		if(pat[pt] == pat[pp])
			skip[++pt] = ++pp;
		else if(pp == 0)
			skip[+pp] = pp;
		else
			pp = skip[pp];
			
	//검색
	pt=pp=0;
	while(txt[pt] !='\0' && pat[pp] != '\0') {
		if(txt[pt] == pat[pp]) {
			pt++; pp++;
		}
		else if (pp == 0)
			pt++;
		else
		    pp = skip[pp];
	}
	if(pat[pp] == '\0')
		return pt - pp;
		
	return -1;
		
	}
	
 }