서로 다른 부분 문자열의 개수 풀이

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

백준 집합과 맵 7단계 - 11478번 서로 다른 부분 문자열의 개수를 풀어보았다.

 

풀이: 브루트 포스 방식으로 부분 문자열을 전부 구하면 된다.

C++에서 중복을 없애기 위해서 벡터를 정렬하고, 그 후에 unique erase를 썼다.

 

C++

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
	string s;
    cin>>s;
    vector<string> v(s.size());
    for(int i=0;i<s.size();i++)
    {
    	for(int j=s.size()-i;j>0;j--)
        {
        	v.push_back(s.substr(i,j));
        }
    }
    sort(v.begin(), v.end()); // erase 쓰기 위해
    v.erase(unique(v.begin(),v.end()),v.end()); // 중복 없애기
    cout<<v.size()-1; // 공백 없애기
}

Python

s=input()
result=set()
for i in range(len(s)):
	for j in range(i,len(s)):
		result.add(s[i:j+1])
print(len(result))

Java