문제

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

풀이

시간초과

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

unordered_set<string> myset; // 중복 제거해서 저장 

void sliceString(string str, int len){ 
	for(int i = 0; i < str.size(); i++){ // N 
		string sub1 = str.substr(i, len); // len (최대 N) 
		myset.insert(sub1); // logN 
	}
}

int main()
{
	string str; 
	cin >> str; 

	// ababc 
	// 1 a b a b c 
	// 2 ab ba ab bc c 
	// 3 aba bab abc bc c 
	// 4 abab babc abc bc c 
	// 5 ababc babc abc bc c 
	for(int i = 1; i <= str.size(); i++){ // N 
		sliceString(str, i); 
	}

	cout << myset.size(); 

	return 0; 
}

이 방법은 문자열을 자르기 시작하는 위치에 따라 자르는 길이가 달라지지 않고 항상 문자열 끝까지 자르기 때문에 비효율적이다. 자르기 시작하는 위치가 뒤쪽으로 이동할수록 자르는 길이는 줄어들어야 하는데 그렇지 않기 때문에 중복되는 부분 문자열이 많이 생긴다.

답안

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

unordered_set<string> myset; // 중복 제거해서 저장 

int main()
{
	string str; 
	cin >> str; 

	// ababc 
	// a ab aba abab ababc
	// b ba bab babc 
	// a ab abc 
	// b bc 
	// c 
	int len = str.size(); 
	for(int i = 0; i < len; i++){ // N 
		// i + j 
		// 0 + 1~5 
		// 1 + 1~4 
		// 2 + 1~3 
		// 3 + 1~2
		// 4 + 1 
		for(int j = 1; j <= len - i; j++){ // N 
			string token = str.substr(i, j); // len (최대 N) 
			myset.insert(token); // logN 
		}
	}

	cout << myset.size(); 

	return 0; 
}

이 방법은 자르기 시작하는 위치(i)가 뒤쪽으로 이동함에 따라 자르는 길이(j)는 줄어든다.