16916번: 부분 문자열 
문제 링크: 16916번: 부분 문자열
개요
문자열이 두 개 주어지면, 두 번째 문자열이 첫 번째 문자열의 부분 문자열인지만 판단하면 되는 간단해 보이는 문제이다. 쉽게 떠오르는 방법인 브루트 포스로 풀면 문자열 길이가 n일 때 시간복잡도가 O(n^2)이 되는데, n이 최대 100만이므로 시간 초과를 피할 수 없다. 이 때 필요한 게 KMP 알고리즘이다. KMP 알고리즘에 대해 KMP : 문자열 검색 알고리즘에 잘 나와있다.
백준에서 KMP 알고리즘을 사용해야 하는 문제는 대부분 골드3 이상에 배정되고 있지만, 이 문제의 경우 파이썬의 in 키워드와 c/cpp의 strstr 함수를 이용해 쉽게 풀리기 때문에 브론즈와 골드로 난이도 기여가 갈려서, 애매한 실버1에 배정된 상태이다.
이 글에서는 strstr 함수를 이용하지 않고 KMP 알고리즘을 이용하여 풀이하겠다.
풀이
makePi 함수
1
2
3
4
5
6
7
void makePi() {
int j = 0;
for (int i = 1; i < len2; i++) {
while (j > 0 && str2[i] != str2[j]) j = pi[j - 1];
if (str2[i] == str2[j]) pi[i] = ++j;
}
}
이 함수는 str2만 이용해서 pi 배열을 채우는 작업을 해준다. pi[i]는 str[0 ~ i]에 대해 가장 긴 접두사이자 접미사인 문자열의 길이이다.
i는 접미사의 마지막 인덱스(현재 취급하는 문자열의 마지막 인덱스), j는 접두사의 마지막 인덱스가 되도록 유지하는 것이 핵심이다.
while문에 도착했을 때, str2[0 ~ j-1]은 str2[0 ~ i-1]에 대해 접두사이자 접미사임을 유지하고 있는 상태이다.
이 때 str2[i] == str2[j]인 경우, str2[0 ~ j]은 str2[0 ~ i]에 대해 접두사이자 접미사이기 때문에 pi[i]는 j+1(j가 0부터 시작하는 인덱스이기 때문에 길이는 그 문자까지의 길이는 j+1이 된다)이며, 다음 탐색을 위해 j를 1 증가시킨다.
str2[i] != str2[j]인 경우, 접두사이자 접미사일 가능성이 있는 곳까지 j를 감소시켜야 한다. pi[j - 1]은 str2 길이가 j인 부분 문자열의 접두사이자 접미사인 문자열의 길이이므로, j를 pi[j - 1]로 변화시키면 여전히 str2[0 ~ j-1]은 str2[0 ~ i-1]에 대해 접두사이자 접미사이다. 따라서 while문을 반복하여 j가 0이 되거나 우리가 원하는 j를 찾으면 탈출하게 된다.
kmp 함수
1
2
3
4
5
6
7
8
void kmp() {
int j = 0;
for (int i = 0; i < len1 && !isSubStr; i++) {
while (str1[i] != str2[j] && j > 0) j = pi[j - 1];
if (str1[i] == str2[j]) j++;
if (j == len2) isSubStr = 1;;
}
}
이 함수를 이용하면 str2가 str1의 부분 문자열로 나타나는 부분을 전부 찾을 수 있다. 그러나 우리는 부분 문자열 여부만 판단하면 되기 때문에 처음 부분 문자열이 나타나는 곳을 찾으면 isSubStr을 1로 바꾸고 탐색을 중단할 것이다.
i는 str1에서 현재 여기까지 탐색했다는 것을 나타내며, for문을 돌며 일정하게 증가한다. j는 str2에서 현재 여기까지 일치했다는 것을 나타낸다.
while문을 만났을 때, str2[0 ~ j-1]과 str1[i-j ~ i-1]은 일치한 상태이다.
이 때 str1[i] == str2[j]인 경우, str2[0 ~ j]과 str1[i-j ~ i]이 일치한 상태인 게 확인된 것이며, 이 때 j를 1 증가시켜준다. 그 이후 j가 str2의 길이인 len2와 같다면 str1의 어느 부분과 str2이 전부 일치한 것이 확인됐으므로 isSubStr을 1로 바꿔준다. str1[i] != str2[j]인 경우, str2[0 ~ j-1]과 str1[i-j ~ i-1]는 일치했지만 더이상 일치하지 않는다는 의미이므로 str1에서 str2이 일치하기 시작한 위치를 바꿔줘야 한다(j를 바꿔줘야 한다). 우리는 pi 배열을 미리 구해놨기 때문에, 현재 j보다 작으면서 str2[0 ~ j]과 str1[i-j ~ i]가 일치하는 j의 최댓값이 pi[j-1]임을 알 수 있다.
전체 코드
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
#include <iostream>
#include <cstring>
#pragma warning(disable:4996)
#pragma warning(disable:6031)
using namespace std;
#define MAX_LEN 1000000
char str1[MAX_LEN + 1], str2[MAX_LEN + 1];
int pi[MAX_LEN + 1] = { 0 }, len1, len2, isSubStr = 0;
void makePi();
void kmp();
int main() {
scanf("%s", str1);
scanf("%s", str2);
len1 = strlen(str1);
len2 = strlen(str2);
makePi();
kmp();
printf("%d", isSubStr);
return 0;
}
void makePi() {
int j = 0;
for (int i = 1; i < len2; i++) {
while (j > 0 && str2[i] != str2[j]) j = pi[j - 1];
if (str2[i] == str2[j]) pi[i] = ++j;
}
}
void kmp() {
int j = 0;
for (int i = 0; i < len1 && !isSubStr; i++) {
while (str1[i] != str2[j] && j > 0) j = pi[j - 1];
if (str1[i] == str2[j]) j++;
if (j == len2) isSubStr = 1;;
}
}