검색 알고리즘 (C)

브루트포스

브루트포스 알고리즘은 그냥 하나하나 다 해보는 알고리즘이다. 검색할 문자열의 크키가 M이고 검색 당하는 문자열의 크기가 N이면 시간 복잡도는 O(NM)이 되는 것이다.

KMP

KMP는 브루트포스보단 더 빠른 알고리즘이다. 이는 건너뛰기 위한 표를 만들어서 작성된만큼 건너뛴다.
전체 배열 a 중에서 검색할 배열을 b라고하자. a의 첫번째 char과 b의 첫번째 char이 일치하지 않으면 다음 a의 두번째 char과 b의 첫번째 char을 비교해야하는 것은 당연한 것이다.
만약 첫번째끼리만 일치했다면? 그것도 한칸 뒤로 옮겨야한다. 하지만 첫번째 두번째 char이 일치하고 다음 세번째는 일치하지 않는다면 다음 조사는 2칸을 뛰어넘어도 된다.
건너뛰기 표에 겹친 char 수를 저장해놓고 다음 조사에는 그에따라 뛰어넘은다음 조사하면 되는 것이다.
시간복잡도는 가장 나쁘더라도 O(N)이다.
코드는 다음과 같다.

int kmp(const char txt[]. const char pat[]) {

	int pt = 1;
    int pp = 0;
    int skip[1024];
    
    skip[pt] = 0;
    while(pat[pt] != '\0') {
    	if(pat[pt] == pat[pp])
        	skip[++pt] = ++pp;
        else if(pp == 0)
        	skip[++pt] = 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;
}

보이어-무어(Boyer-Moore)

보이어-무어법은 현재에도 많이쓰이는 알고리즘이다.

1. Bad Character Shift (나쁜 문자 이동)
2. Good Suffix Shift (착한 접미부 이동)

이 두가지로 나눌 수 있는데 첫번째는 처음에 대치를 하고 뒤부터 봤을 때, 일치하지 않는 문자를 찾는다. 그리고 그 문자가 나오는 부분을 뒤에서 찾아 다시 대치해 비교하는 방법이다. 예를들어,
abedefcbe
cbe
이면, 패턴의 뒤에서부터 봤을 때 e는 일치하고 b도 일치한다. c가 일치하지 않으므로 다음에 나오는 c를 찾고 이에 패턴을 대치한다. 그럼 다음 단계는
abedefcbe
000000cbe 여서 찾을 수 있다.

두번째는 둘다 맨앞에 배치한 뒤, b 맨 뒤의 문자와 a와 비교한다.

1. 배열 b에 포함되어 있지 않은 문자일 경우
   배열 b의 크기 n만큼 뒤로 뜀.
2. 배열 b에 포함되어있는 문자를 만난 경우
   배열 b에서 그 문자의 마지막 index = k, n-k-1만큼 뜀(n에서 인덱스를 빼면 겹치는 부분만 나온다. 인덱스는 0부터 시작하므로 1을 더 빼준 것이다.)
   • 만약 배열 b에서 그 문자가 하나뿐이라면 n만큼 뜀

이런 단계를 거치기 위해서는 이도 마찬가지로 건너뛰기 표가 필요하다.
시간복잡도는 가장 나쁜 경우 O(N), 평균 O(N/M)이다.
코드는 다음과 같다.

int bm (cosnt char txt[], const char pat[]) {
	int pt;
    int pp;
    int txt_len = strlen(txt);
    int pat_len = strlen(pat);
    int skip[UCHAR_MAX; pt++];
    for(pt=0; pt <= UCHAR_MAXl 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;
        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;
}