[4] KMP 패턴 매칭
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&&j < 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) 시간 안에 패턴 매칭 여부를 알 수 있다.