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

#include <iostream>
#include <string>
#include <set>

using namespace std;

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

	set<string> result;
	
	for (int i = 0;i < s.size();i++) {
		string s1 = "";
		for (int j = i;j < s.size();j++) {
			s1 += s[j];
			result.insert(s1);
		}
	}

	cout << result.size();
}

우선 알파벳들을 입력받고, 서로 다른 문자열의 개수를 세어야 하기 때문에 중복을 무시하는 set을 사용할 것이다. set에 담아줄 건데, 이중 for문을 사용할 것이다.

여기서 헷갈림 주의!

 

i가 0일 때를 시작으로 string s1="";로 초기화해준다. 그 상태에서 j가 늘어남에 따라 set에 넣을 건데

만약 처음에 입력한 string값이 hongsi라고 해보자. 그러면 맨 처음에 set에 들어가는 값은 h가 될 것이다. 여기까진 ok

다음으로 들어가는 것은 s1+='o'가 될 것이다. 그럼 앞에 h가 있었기 때문에 그냥 추가로 o가 더해져 ho가 set에 들어갈 것이다. 이렇게 h, ho, hon, hong, hongs, hongsi

모두 입력되고 나면 i가 0에서 1로 바뀌고, 그 뒤로는 o, on, ong, ongs, ongsi 이런 식으로 집합에 들어가게 될 것이다. 

이때 중복되는 것은 제외되며 저장된다.

 

백준 기본 문제로 내준 ababc에서는 이렇게 하면 set의 size가 12로 나올 것이다.

성공!