Notice
Recent Posts
Recent Comments
Link
«   2025/07   »
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
Tags
more
Archives
Today
Total
관리 메뉴

Mini

백준16916 // cpp 문자열 포함검사 O(N+M), strstr vs find 본문

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();
}