SW Expert Academy 의 1213번 문제입니다.
본문이 되는 영어 문자열이 주어지고, 거기에서 특정한 패턴이 몇 번 나오는지 찾는 문제입니다.
이전까지 다루었던 문자열 검색 알고리즘을 사용한다면 어렵지 않게 풀릴 것 같습니다.
저는 미리 구현해 놓았던 KMP 알고리즘 소스코드를 사용해 보았습니다.
- 난이도 : 1~2
문제 조건
총 10개의 테스트 케이스가 주어진다.
input으로 주어지는 문장의 길이는 1000자를 넘지 않는다.
한 문장에서 검색할 문자열 길이는 최대 10이다.
한 문장에서는 한 가지 패턴만 검색한다.
Input
첫 줄에는 테스트 케이스 번호, 그 다음줄에는 찾을 패턴, 그 다음줄에는 검색할 문장(본문)이 주어진다.
Output
찾고자 하는 패턴이 몇 번 나오는지 그 횟수를 출력한다.
소스코드 (KMP 알고리즘 활용)
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
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int* table;
int findCnt;
int* createTable(char* string, int stringLen) {
int j;
table = (int*)malloc(sizeof(int) * (stringLen + 1));
table[0] = -1;
for (int i = 1; i < stringLen + 1; i++)
table[i] = 0;
j = 0;
for (int k = 1; k < stringLen; k++) {
while (string[j] != string[k] && j > 0) {
j = table[j];
}
if (string[j] == string[k])
table[k+1] = ++j;
}
return table;
}
void KMP(char *string, char *pattern) {
int* table;
int stringLen = strlen(string);
int patternLen = strlen(pattern);
int distance = 0, idx = 0, cnt = 0;
int findFlag = 0;
table = createTable(pattern, patternLen); // 최대 경계 너비 테이블 채우기
while(1) {
idx = 0;
// 허용 범위를 벗어나면 반복문 나가기
if ((idx + distance) + patternLen > stringLen)
break;
while(string[idx+distance] == pattern[cnt]){
cnt++; // 일치 갯수 증가
idx++;// 인덱스 증가
if (cnt == patternLen) {
findFlag = 1; findCnt++;
break;
}
}
distance = distance + (cnt - table[cnt]); // 이동거리 계산
cnt = 0; // 일치 갯수 초기화
}
if (findFlag == 0)
printf("해당 패턴을 찾지 못했습니다.\n");
}
int main() {
char parent[1000];
char str[10];
int test_case;
for(int T = 0; T < 10; T++){
scanf("%d",&test_case);
scanf("%s",str);
scanf("%s",parent);
KMP(parent, str);
printf("#%d %d\n", test_case, findCnt);
findCnt = 0;
}
}
실행 결과, 6ms 의 실행 속도를 보였습니다.
즉 KMP 알고리즘을 통해 꽤나 준수한 탐색 속도를 보여 준다고 할 수 있습니다.
만일 Brute force 방식으로 하나하나 앞에서 찾았다면 훨씬 느렸을 것입니다.