7-4장 보이어-무어법

1. 보이어-무어법 살펴보기 

 

 - 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 결정

 

 - Good Suffix method

 : 접미사와 같은 문자열이 패턴 문자열 내에 존재하는지 검사 

 -Bad Character method

 : 본문의 문자열과 패턴이 불일치하는 문자 (나쁜 문자)를 발견하면 패턴의 나쁜 문자와 텍스트의 나쁜 문자를 일치 시킴

 

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

 

- 1) 텍스트와 패턴의 첫 번째 문자를 위, 아래로 겹치고 패턴의 마지막 문자 'C'를 검사 

- 텍스트의 'X'는 패턴에 없음

- 텍스트 안에서 패턴에 들어 있지 않은 문자를 찾으면 해당 위치까지의 문자는 건너 뛸 수 있음

- 2)~4)의 비교는 생략하고 패턴을 4칸 뒤로 옮김

 

 

- 패턴의 마지막 문자 'C'와 텍스트의 'C'가 일치하기 때문에 패턴의 1칸 앞의 문자 'A'로 옮길 수 있음

- 'Z'는 패턴에 없는 문자이므로 3칸 이동 

- 2)와 같이 패턴의 뒤쪽에 위치한 'A'가 텍스트와 위, 아래로 겹치도록 패턴을 1칸 옮김

- 4)와 같은 방법으로 3칸 이동 하면 안됨 

- 2)에서 패턴과 텍스트의 모든 문자가 일치하므로 검색 성공!

 

- 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표(건너뛰기표)

- 패턴 문자열의 길이 n

 

 1) 패턴에 들어 있지 않은 문자를 만난 경우 

  - 패턴을 옮길 크기는 n

 

 2) 패턴에 들어 있는 문자를 만난 경우 

  - 마지막에 나오는 위치의 인덱스가 k이면 패턴을 옮길 크기는 n-k-1

  - 같은 문자가 패턴안에 중복해서 들어 있지 않다면 패턴을 옮길 크기는 n

 

- 보이어 -무어법으로 문자열을 검색하는 프로그램

//보이어-무어법으로 문자열을 검색하는 프로그램
#include <stdio.h> 
#include <string.h>
#include <limits.h>

//보이어-무어법으로 문자열을 검색하는 함수 
int bm_match(const char txt[], const char pat[]) 
{
	int pt; //txt 커서 
	int pp; //pat 커서 
	int txt_len = strlen(txt); //txt 문자 개수 
	int pat_len = strlen(pat); //pat 문자 개수 
	int skip[UCHAR_MAX+1]; //건너뛰기 표 
	//건너뛰기 표 만들기 
	for(pt = 0; pt <= UCHAR_MAX; pt++) 
		skip[pt] = pat_len;
	for(pt = 0; pt < pat_len -1; pt++)
		skip[pat[pt]] = pat_len - pt -1;
		
	while(pt < txt_len) {
		pp = pat_len -1; //pat의 마지막 문자부터 검사 
		while(txt[pt] == pat[pp]) {
			if(pp == 0)
				return pt;
			pp--;
			pt--;
		}
		pt += (skip[txt[pt]] >pat_len - pp) ? skip[txt[pt]] : pat_len - pp;
	}
	return -1;
}

int main()
{
	char s1[256]; //텍스트 
	char s2[256]; //패턴
	puts("보이어-무어법 ");
	printf("텍스트:");
	scanf("%s",s1);
	printf("패턴:");
	scanf("%s",s2);
	
	int idx = bm_match(s1,s2); //문자열 s1에서 문자열 s2를 보이어-무어법을 사용해 검색
	if(idx == -1)
		puts("텍스트에 패턴이 없습니다.");
	else
		printf("%d번째 문자부터 match합니다.\n",idx+1);
	
	return 0;
}

 

 

2. strstr 함수 알아보기 

 

strstr 함수 

- 문자열 검색 

- char *strstr(const char *s1, const char *s2);

- s1이 가리키는 문자열에서 s2가 가리키는 문자열과 일치하는 (널문자를 포함하지 않는) 문자열을 찾음

 가장 앞쪽에 나오는 문자열을 찾음

 

- strstr 함수를 사용한 프로그램

//strstr함수를 사용한 프로그램
#include <stdio.h> 
#include <string.h>

int main()
{
	char s1[256], s2[256];
	puts("strstr함수");
	printf("텍스트 :"); 
	scanf("%s",&s1);
	printf("패턴:");
	scanf("%s",&s2);
	
	char *p = strstr(s1,s2); //문자열 s1에서 문자열 s2를 검색 
	if(p == NULL) 
		printf("텍스트에 패턴이 없습니다.\n");
	else {
		int ofs = p -s1;
		printf("\n%s\n",s1);
		printf("%*s|\n",ofs,"");
		printf("%*s%s\n",ofs,"",s2);
	} 
	
	return 0;
}