자료구조

[4] KMP 패턴 매칭

지식보부상님 2021. 1. 7. 20:19

KMP(Knuth, Morris, Pratt) 패턴 매칭 알고리즘은 O(n)의 시간 복잡도를 갖는 알고리즘으로,

특정 패턴이 문자열에 존재하는지 확인하는 함수이다.

 

KMP 패턴 매칭 알고리즘을 알기 위해서는 실패함수를 알아야한다.

 

실패함수(failure function)

 

실패함수 f( j ) 는 j 번째 index 에서 접두사와 접미사가 일치하는 최대의 길이를 의미한다. 

접두사와 접미사가 일치하는 최대 길이가 존재하지 않으면 -1로 설정한다.

 

예를들어 패턴 p가 p = abcabcacab 라고 하자

당연히 f( 0 ) = -1 이다. 

다음으로 f( 1 )을 보면 패턴에서 인덱스 1보다 작은 부분이 인덱스 1과 동일하게 일치하는 부분이 없으므로

마찬가지로 f( 1 ) = -1 이다.

마찬가지로 f( 2 ) = -1이다. 

 

다음으로 f( 3 )을 보면, 패턴에서 인덱스 3보다 작은 부분에서 인덱스 3과 동일하게 일치하는 부분은 인덱스가 0일 때 이므로 f( 3 ) = 0 이다.

 

다음으로 f( 4 )를 보면, 패턴에서 인덱스 4보다 작은 부분에서 ab로 일치하는 부분이 인덱스 0에서 1까지 ab 이므로

f( 4 ) = 1이다.

 

다음으로 f( 5 ) 를 보면, 패턴에서 인덱스 5보다 작은 부분에서 abc 로 일치하는 부분이 인덱스 0에서 2까지 abc로 존재하므로, f( 5 ) = 2 이다. 

 

다음으로 f( 6 )을 보면, 패턴에서 인덱스 6보다 작은 부분에서 abca로 일치되는 부분은 인덱스 0에서 3까지 abca 로 존재하므로, f( 6 ) = 3이다.

 

그 다음으로 f( 7 )을 보면, 패턴에서 인덱스 7보다 작은 부분에서 abcac로 일치하는 부분은 존재하지 않으므로,

f ( 7 ) = -1 이 된다.

 

다음으로 f( 8 )을 보면, 패턴에서 인덱스 8보다 작은 부분에서 a로 일치하는 부분은 인덱스 0일 때이므로,

f( 8 ) = 0 이다. 

 

마지막으로 f( 9 )를 보면, 패턴에서 인덱스 9보다 작은 부분에서 ab로 일치하는 부분은 인덱스 0에서 1까지 ab이므로,

f( 9 ) = 1 이다.

 

C 언어 코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max_string 100
#define max_pat 100
 
int pmatch(); //kmp 알고리즘, 패턴이 있다면 패턴의 시작 위치의 인덱스를 리턴한다.
void fail(); //실패함수를 만들어 주는 함수
 
int failure[max_pat]; //실패함수
char string[max_string]; //주어지는 문자열을 저장
char pat[max_pat]; //주어지는 패턴을 저장
 
int main() {
    FILE *fp;
    int n;
    fp = fopen("kmp.txt""r");
    if (!fp) {
        fprintf(stderr, "file open error\n");
        exit(1);
    }
    fscanf(fp, "%s"string); //문자열 받는다.
    fscanf(fp, "%s", pat); //패턴 받는다.
    fclose(fp);
    n = pmatch();
    printf("%d\n", n);
    system("pause");
    return 0;
 
}
 
int pmatch() {
    int i = 0, j = 0//i는 문자열, j는 패턴의 index
    int lens, lenp;
    lens = strlen(string); //주어진 문자열의 길이
    lenp = strlen(pat); //주어진 패턴의 길이
    while (i < lens&&< lenp) { //index가 범위 내에 있을 동안 패턴과 문자열을 비교한다. 
        if (string[i] == pat[j]) { //패턴과 문자열의 문자가 일치한다면, 패턴과 문자열의 다음 문자를 비교
            i++;
            j++;
        }
        else if (j == 0)    i++//패턴의 처음과 문자열의 문자가 다르다면,문자열은 다음 문자를 비교하도록 한다.
        else //이전에는 문자열과 패턴이 일치하고, 현재는 다른 문자일 때 
            j = failure[j - 1+ 1//실패함수를 이용하여 패턴의 index를 결정한다. 
    }
    return ((j == lenp) ? (i - lenp) :- 1);  //패턴의 끝까지 index가 진행됐다면 문자열 안에 패턴과 일치하는 부분이 있다는 뜻이고, 그 위치는 i-패턴의 길이 이다. 없다면 -1 리턴
}
 
void fail() {
    int i, j; //j는 패턴에서 계속 이동하는 index, i는 실패 함수의 값을 결정해주는 값 
    int n = strlen(pat);
    failure[0= -1;
    for (j = 0;j < n;j++) { //계속해서 하나씩 이동시켜 패턴 함수를 완성시킨다. 
        i = failure[j - 1]; //바로 앞의 실패함수를 이용하여 현재 실패함수의 값을 결정한다.  
        while ((pat[j] != pat[i + 1]) && (i >= 0)) //앞의 실패함수 값이 -1이 아니고, 그 값이 가리키는 패턴 문자와 현재 패턴 문자가 다를 경우
            i = failure[i]; //계속해서 실패함수가 가리키는 패턴 문자로 이동시켜 준다 .
        if (pat[j] == pat[i + 1]) //앞에서 결정한 인덱스 i의 바로 다음 패턴의 문자와 현재 문자를 비교하여 같으면
            failure[j] = i + 1//그 문자의 index를 실패함수의 값으로 결정하고
        else failure[j] = - 1//다르면 처음부터 다시 패턴 비교를 시작해야 하므로 -1로 결정짓는다. 
    }
}
 
cs

위는 kmp.txt 파일을 input으로 받아 제시된 string에서 패턴이 있는지 확인하고,

있다면 시작 index를 출력, 없다면 -1을 출력하는 프로그램이다.

 

kmp.txt 파일은 첫줄은 문자열, 둘째 줄은 pattern에 대한 정보를 저장하고 있다.

 

KMP_pattern_matching 함수의 시간 복잡도는 O(strlen(string)) 이고,

fail_funcion 함수의 시간 복잡도는 O(strlen(pattern)) 이 되어

 

총 KMP 패턴 매칭 알고리즘의 시간 복잡도는 O( strlen(string) + strlen(pattern) ) 이 되어

O(n) 시간 안에 패턴 매칭 여부를 알 수 있다.