백준 11478 - 서로 다른 부분 문자열의 개수(C++)

문제 링크입니다. https://www.acmicpc.net/problem/11478

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

부분 문자열의 개수를 구하는 문제입니다.

 

부분 문자열의 개수를 구하는 문제입니다.

 

문자열의 길이가 1 ~ N까지 있지만 1번 문자부터 마지막 문자까지 문자열을 만들어 가면 됩니다.

 

예를 들어, ababc의 경우

a에서 시작해 a -> ab -> aba -> abab -> ababc로 만들 수 있습니다.

다음은 b에서 시작해 b -> ba -> bab -> babc가 되며

다음은 a에서 시작해 a -> ab -> abc가 됩니다.

이를 계속 반복해서 끝까지 구하면 됩니다.

 

그렇다면 구해진 문자열이 이전에 나온 것과 같은 것인지를 확인하는 방법은 map을 사용하는 것입니다.

 

map는 값을 저장만 한다면 순서에 상관없이 저장되기에 이전의 값을 편리하게 찾을 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;

string N;
map<string, int> String;

void solve(){
    int cnt = 0;
    for(int i = 0; i < N.size(); i++){
        string x = "";
        for(int j = i; j < N.size(); j++){
            x += N[j];
            if(String.find(x) == String.end()){
                String.insert({x, 1});
                cnt++;
            }
        }
    }
    cout << cnt;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.