KMP String matching

문자열 S, P가있고, S에서 P를 검색한다고 할때, 가장 기초적인건 아래와 같이 검색을 합니다.

비효율적인부분이 있습니다.  그래서 Knuth, Morris, Pratt 세 사람이 만든 KMP 알고리즘을 지금 설명하려고 합니다.

제가 이해한것을 풀어쓰는거라 잘못 이해한 것이 있을 수도 있습니다.

그럴때는 말씀해주시면 감사하겠습니다.

 

KMP는 패턴을 만들어서 검사에 실패했을때 다음 검사에서 불필요한 부분을 생략하는데 있습니다.

위 그림은 검사에 실패했을때 P를 오른쪽으로 한칸 이동하지만 KMP는 안해도 되는부분은 과감히 건너뜁니다.

 

KMP는 크게 나눠보면 찾고자하는 문자열에 패턴을 구하고 그 패턴을 이용해서 검사를 하는 것입니다.

문자열 페턴 구하는것을 설명하기에 앞서 suffix, prefix에 대해 알아봅시다.

 

문자열 abcdabc에 대한 suffix, prefix는

prefix suffix  1  a  c  2  ab  bc  3  abc  abc  4  abcd  dabc  5  abcda  cdabc  6  abcdab  bcdabc  7  abcdabc  abcdabc

3번 열을 보면 'abc', 'abc'같죠?  [ 마지막 전체 비교는 필요없는거죠....허허]

패턴을 찾는건 suffix와 prefix가 같은 부분을 찾는다고 할수 있습니다.

 

[a는 할필요가 없겠죠?]

ab, abc, abcd, abcda, abcdab, abcdabc에 대한 suffix, prefix가 같으면서 가장 긴~부분을 찾는 것이죠.

index 5, 문자 'b'를 예로 들면,  abcda까지 문자열 매칭이 됐는데, b에서 틀릴경우 1번째 문자로 이동하라는 얘기입니다.

1	a	a
2	ab	da
3	abc	cda
4	abcd	bcda
5	abcda	abcda

첫번째문자 'a'와 마지막 문자 'a'가 같으니 이동해도 문제없겠죠?

 

6번째 문자 C의 경우, 매칭된 문자열은 abcab이고   최대 prefix, suffix는   ab이므로  2가 들어간것이죠~ : )

c,6이 실패했을때 진행방향이 틀렸네요;; d,3이 아니라 c,2로 이동하는게 맞습니다. 2010/12/01

틀렸는데도 아무 댓글이 없다는게 쓸쓸하네요......ㅠ,.ㅠ ㅋㅋ

소스는 아래와 같습니다.

/*main.cpp*/
#include "kmp.h"
#include <string.h>

int main()
{
        char pattern[50];
        char strings[100];

        int pattern_size;
        int strings_size;
        char *find;

        printf("Enter the pattern :");
        scanf("%s", pattern);
        
        pattern_size = strlen(pattern);

	strcpy(strings, "aabaccabaabcdabd");
        strings_size = strlen(strings);


        make_table(pattern, pattern_size);

        find = (char*)kmp_matching(strings, strings_size, pattern, pattern_size);

		if ( find != NULL )
			printf("Find String matching : %d\n", find-strings);
		else
			printf("Fined is null\n");

        return 0;
}

/*kmp.cpp*/
#include "kmp.h"

char* Table;

void make_table(char *pattern, int pattern_size)
{
        int i, j;
        i = 0, j = 1;
        Table = (char*)malloc(sizeof(char)*(pattern_size+1));
        Table[0] = -1;

        while ( j < pattern_size)
        {
                if ( pattern[i] == pattern[j] )
                {
                        Table[j] = i;
                        i++;
                        j++;
                }
                else{
                        Table[j] = i;
                        i = 0;
                        j++;
                }
        }
        for ( i = 0; i < pattern_size; i++ )
        {
                printf("%d's table : %d\n", i, Table[i]);
        }
}


char* kmp_matching(char* strings, int strings_size, char* pattern, int pattern_size)
{
        int str_point, pat_point;
        str_point = 0, pat_point = 0;

        while ( str_point < strings_size - pattern_size + 1 )
        {
                if ( strings[str_point+pat_point] == pattern[pat_point] )
                {
                        pat_point++;
                        if ( pat_point == pattern_size )
                        {
                                return strings+str_point;
                        }
                }
                else
                {
                        if ( pat_point == 0  || Table[pat_point] == 0)
						{
							str_point++; 
							pat_point = 0; 
						}
						
						else 
						{
							str_point += pat_point;
							pat_point = Table[pat_point];
						}
                }
        }

		free(Table);
        return NULL;
        
}

/*kmp.h*/
#ifndef _KMP_H_INCLUDE
#define _KMP_H_INCLUDE
        #include <stdio.h>
        #include <stdlib.h>

        void make_table(char* pattern, int pattern_size);
        char* kmp_matching(char* strings, int strings_size, char* pattern, \
                                int pattern_size);
#endif