[BOJ] #16916 - 부분 문자열

December 3, 2022

👻 부분 문자열

🌱 문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, “aek”, “joo”, “ekj”는 “beakjoon”의 부분 문자열이고, “bak”, “p”, “oone”는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

시간 제한 : 1초
메모리 제한 : 512 MB

🌱 입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

🌱 출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

🌱 예제

🪐 입출력 1

입력
```
baekjoon
aek
```
출력
```
1
```

🪐 입출력 2

입력
```
baekjoon
bak
```
출력
```
0
```

🪐 입출력 3

입력
```
baekjoon
joo
```
출력
```
1
```

🪐 입출력 4

입력
```
baekjoon
oone
```
출력
```
0
```

🪐 입출력 5

입력
```
baekjoon
online
```
출력
```
0
```

🪐 입출력 6

입력
```
baekjoon
baekjoon
```
출력
```
1
```

👻 풀이

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
string S, P;
int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 부분 문자열
    cin >> S >> P;
    if(strstr(S.c_str(), P.c_str()) != nullptr) cout << '1';
    else cout << '0';
    return 0;
}

시간 : 24 ms
메모리 : 5124 KB

👻 글을 마치며

해당 문제는 쉽게 풀 수 있었는데 시간 초과가 여러번 걸렸다. 처음에는 find와 substr를 사용했었는데, 주어지는 문자열의 최대 길이가 100만이라 아마 그렇게 뜬 것 같다. 찾아보니, 문자열에 해당 문자열이 포함했는지를 알려주는 strstr 함수가 있다는 것을 알게되었다. find와 strstr는 기본적으로 동일한 시간 복잡도 O(NM)을 가지지만, strstr은 일부 환경에서 (정확히는 GCC의 라이브러리 구현인 libstdc++에서) O(N+M) 시간 복잡도의 알고리즘으로 구현되어 있다고 한다.

소스코드 보러가기