[알고리즘] 백준 11478 - 서로 다른 부분 문자열의 개수

실버 3 🪴
https://www.acmicpc.net/problem/11478

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

문제 설명

문자열 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	return
ababc	12

---

해결방법

반복문을 두번 돌면서 문자열을 자르면 된다. 처음부터 한번에 이중 반복문을 만들려고 하니 꼬였다. 그래서 안쪽 반복문을 여러개 만들어서 규칙을 찾아서 만들었다.

set 자료형은 중복된 값을 허용하지 않는 집합이다. insert 로 값을 넣을 수 있다.

str.substr(첫문자의 위치, 자를 길이) 이다. 다른 언어에서 비슷한 기능을 하는 메소드처럼 (idx, idx - 1) 범위를 지정하는게 아니다.

코드

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

using namespace std;

int main(void) {
    string str;
    set<string> answer;

    cin >> str;
    for (int i = 1; i <= str.length(); i++)
    {
        for (int j = 0; j + i <= str.length(); j++)
            answer.insert(str.substr(j, i));
    }
    cout << answer.size();
    return 0;
}