[BOJ-11478][C++] 서로 다른 부분 문자열의 개수

문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

 

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

 

출력

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

 

예제 입력 1

ababc

 

예제 출력 1

12

 

알고리즘 분류

• 자료 구조
• 문자열
• 해시를 사용한 집합과 맵
• 트리를 사용한 집합과 맵

 

문제 출처

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

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

 

---

 

문제 해결 방법

• unordered_map과 string을 이용하여 문제를 해결하였다.
• string 객체의 substr(a, b) 메서드는 [a, a + b) 범위의 부분열(Substring)을 반환해준다.
• 따라서 다음과 같이 사용하면, 입력받은 문자열로부터 만들 수 있는 모든 종류의 문자열을 뽑아낼 수 있다.

for (int i = 0; i < S.size(); i++) {
    for (int j = 0; j < S.size(); j++) {
        tmp = S.substr(i, j + 1);
        um[tmp]++;
    }
}

• 이 문자열을 뽑아내서 unordered_map 객체(unordered_map<string, int> um)의 키(Key)로 넣어주고, 넣어줄 때마다 값(Value)을 하나씩 증가시켜준다. (um[tmp]++)
• 맵 객체에는 중복되지 않은 고유한 키(Key)만 남게 되며, 이 키(Key)의 개수를 출력해주면 된다.

cout << um.size() << '\n';

 

코드

#include <iostream>
#include <unordered_map>
using namespace std;

int cnt;
string S, tmp;
unordered_map<string, int> um;

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

    cin >> S;

    for (int i = 0; i < S.size(); i++) {
        for (int j = 0; j < S.size(); j++) {
            tmp = S.substr(i, j + 1);
            um[tmp]++;
        }
    }

    cout << um.size() << '\n';

    return 0;
}

 

채점 결과

위 : unordered_map 사용, 아래 : map 사용 / unordered_map이 약간 더 빠르다.

 

참고

• [단계별로 풀어보기] > [집합과 맵]
• 실버III