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

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

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

풀이 :

문자보다 이해하기 쉽게 숫자로 본다면,

01234가 있다고 가정

0에서 시작해서

0, 01, 012, 0123, 01234

1, 12, 123, 1234

2, 23, 234

3, 34

4

이렇게 모든 부분 문자열을 구할 수 있다.

하지만 00000처럼 같은 문자가 존재할 경우 중복으로 저장 될 수 있다.

set은 이미 저장된 원소를 저장하지 않기 때문에 set에 저장하고,

답은 set의 크기가 된다.

 

코드 :

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

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

    string s, subs; //부분 문자열을 저장할 subs 선언
    set<string> ans; //중복 제거를 위해 set 선언 
    cin >> s;
    for(int i=0; i<s.size(); i++){
        subs = ""; //빈 문자열로 초기화
        for(int j=i; j<s.size(); j++){ //각 인덱스로 시작하는 부분 문자열을 구하기 위해 j는 i부터 시작
           subs += s[j]; //s[j]를 더해가며 부분 문자열을 구해준다
           ans.insert(subs); //구해진 문자열은 바로 set에 넣어준다
        }
    }
    cout << ans.size() << '\n';
}