백준 16916 부분 문자열(c++)

https://www.acmicpc.net/problem/16916

16916번: 부분 문자열

<틀린 코드>

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	string s,p;
	cin>>s>>p;
	if(s.find(p)!=string::npos) cout<<1<<'\n';
	else cout<<0<<'\n';
}

이 코드는 시간 복잡도가 1초가 넘어서는 코드이다.

<맞는 코드>

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	string s,p;
	cin>>s>>p;
	char *ptr = strstr((char*)s.c_str(),(char*)p.c_str());
	if(ptr != NULL) cout<<1<<'\n';
	else cout<<0<<'\n';
}

알아보던 도중 c언어와 c++에서 둘다 호환되는 strstr함수에 대해서 알게 되었다.

이는 어셈블리어 최적화를 통해 복잡도 문제를 해결할 수 있다.