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

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

---

반응형

 

📌 접근 방법

⚡ ababc 입력

1. i = 0일 때 : a, ab, aba, abab, ababc
2. i = 1일 때 : b, ba, bab, babc
3. i = 2일 때 : a, ab, abc
4. i = 3일 때 : b, bc
5. i = 4일 때 : c

➡ map 에 넣고 bool로 이미 있는 조합인지 아닌지 체크하며 카운팅

 

✅  Pass Code

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iterator>
#include<map>
#include<set>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    map<string, bool> m;
    string str;
    cin>>str;
    int cnt=0;
    for(int i=0; i<str.length(); i++){
        string tmp="";
        for(int j=i; j<str.length(); j++){
            tmp+=str[j];
            if(m[tmp]==false){
                m[tmp]=true;
                cnt++;
            }
        }
    }
    cout<<cnt<<"\n";
    return 0;
}