[C++] 백준 14단계 - 11478번 문제 (서로 다른 부분 문자열의 개수)

문제설명

 

소스코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    string input;
    int count = 0;
    cin >> input;
    for (int i = 0; i < input.length(); ++i)
    {
        vector<string> vec;
        for (int j = 0; j < input.length() - i; ++j)
        {
            string strTmp = input.substr(j, i + 1); //문자열 잘라내기
            vec.push_back(strTmp); //벡터에 원소 추가
        }
        sort(vec.begin(), vec.end()); //벡터 정렬
        vec.erase(unique(vec.begin(), vec.end()), vec.end()); //중복 항목 제거
        count += vec.size(); //벡터의 원소 개수를 더함
    }
    cout << count;
}

 

설명

문자열 ababc가 주어졌을 때, 벡터인 vec에 들어가는 원소는 아래와 같다.

i	j	원소
0	0	a
	1	b
	2	a - erase에 의해 제거
	3	b - erase에 의해 제거
	4	c
1	0	ab
	1	ba
	2	ab - erase에 의해 제거
	3	bc
2	0	aba
	1	bab
	2	abc
3	0	abab
	1	babc
4	0	ababc