[C++] 백준 11478. 서로 다른 부분 문자열의 개수

문제

시간초과

실버 3인데는 이유가 있는거다
실버 4는 제법 푼다 했는데 바로 막히기

#include <iostream>
#include <string>
#include <set>
using namespace std;

string str;
set<string> s;

int main() {
	cin >> str;

	string tmp;
	for (int i = 1; i <= str.length(); i++) {
		for (int j = 0; j <= str.length() - i; j++) {
			for (int k = j; k < j + i; k++) {
				tmp += str[k];
			}
			s.insert(tmp);
			tmp = "";
		}
	}

	cout << s.size();

	return 0;
}

재도전

뭔가 있었던 것 같은데 라고 생각하며 백준 11478을 구글링하던 고 때 게시글 미리보기에서 힌트를 얻어버렸다.

그것은 바로 substr().
애간장을 태우는 채점 속도였으나 바로 통과가 됐다. 휴
채점 속도가 느린 데에는 메모리가 한 몫 했을 것인데
이것보다 빠른 풀이가 있을테지만
손이 너무 시려워서 패스하겠다(?)

코드

#include <iostream>
#include <string>
#include <set>
using namespace std;

string str;
set<string> s;

int main() {
	cin >> str;

	for (int i = 1; i <= str.length(); i++) {
		for (int j = 0; j <= str.length() - i; j++) {
			s.insert(str.substr(j, i));
		}
	}
	cout << s.size();

	return 0;
}