Algorithm/boj
백준16916 // cpp 문자열 포함검사 O(N+M), strstr vs find
Mini_96
2023. 7. 11. 02:03
https://www.acmicpc.net/problem/16916
16916번: 부분 문자열
첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.
www.acmicpc.net
* cpp 문자열 포함검사 O(N+M)
strstr(문자배열1, 문자배열2)
반환 : 위치 포인터 //못찾으면 NULL
ex)char[] c1= i`m on my way
char[] c2 = way
char[] c3=hpeth
strstr(c1,c2) // return 11
strstr(c1,c3) //return NULL
#include <bits/stdc++.h>
using namespace std;
char s[1000004], p[1000004];
int check() {
if (strstr(s,p)!=NULL) {
return 1;
}
return 0;
}
int main() {
cin >> s >> p;
cout << check();
}
* string1.find(string2)
O(NM)이므로 시간초과가난다.
#include <bits/stdc++.h>
using namespace std;
string s, p;
int check() {
if (s.find(p) != string::npos) {
return 1;
}
return 0;
}
int main() {
cin >> s >> p;
cout << check();
}