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

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

11478번: 서로 다른 부분 문자열의 개수

 

 

해결방법

 

   처음엔 비트마스크 연산을 통해서 모든 부분집합을 구한 뒤(공집합 제외), 벡터에 넣은 뒤 unique 연산을 해서 서로 다른 부분집합의 개수만 출력하려 했는데, set 자료형의 특징을 사용하면 그럴 필요가 없다는 것을 깨달았다.

   set 자료형의 특징

• 중복된 키를 허용하지 않음
• 중복된 키를 insert 해도 추가되지 않음

   따라서 앞의 원소부터 차례대로 경우의 수를 구해준 뒤 무차별적으로 set 컨테이너에 넣으면, 서로 다른 부분집합만 컨테이너에 남게 된다.

 

 

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  

    string str, tmp;
    cin >> str;

    set<string> _set;

    for (int i = 0; i < str.length(); ++i) {
        tmp = "";
        for (int j = i; j < str.length(); ++j) {
            tmp += str[j];
        //    cout << tmp << '\n';
            _set.insert(tmp);
        }
    }

    cout << _set.size();




    return 0;
}