BOJ 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의 서로 다른 부분 문자열의 개수를 출력한다.

풀이#

문자열의 서로 다른 부분 문자열 개수를 세려면 가능한 시작점과 끝점을 모두 만들어 보고, 중복만 제거하면 된다. 코드에서는 substr로 부분 문자열을 만들어 set<string>에 넣기 때문에 같은 부분 문자열이 여러 번 나와도 자동으로 하나만 남는다.

길이가 1000 이하라서 모든 부분 문자열을 생성해도 충분하다. 결국 문제의 핵심은 몇 번 나왔는지가 아니라 서로 다른가이므로, 집합 자료구조가 정확히 들어맞는다.

코드#

#include <iostream>
#include <set>
using namespace std;
 
void solve() {
 
	string str;
	cin >> str;
 
	int len = str.length();
	set<string> s;
 
	for (int i = 0; i < len; i++) {
		
		int x = 0, y = len - i, cnt = 0;
 
		while (cnt <= i) {
 
			string ss = str.substr(x, y);
			s.insert(ss);
 
			x++;
			cnt++;
		}
	}
 
	cout << s.size() << '\n';
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: 모든 부분 문자열을 만들고 집합에 넣으며, 문자열 복사 비용까지 포함하면 $O(N^3 \log N)$이다.
• 공간 복잡도: 서로 다른 부분 문자열을 저장하므로 최악의 경우 $O(N^3)$ 문자 공간을 사용한다.

마무리#

가능한 부분 문자열을 모두 만들고 집합에 넣으면 중복은 자료구조가 제거해 준다. 길이 제한이 작기 때문에 단순 생성 방식으로도 충분하다.