[11478] 서로 다른 부분 문자열의 개수

 

문자열 슬라이싱과 관련된 문제이다

string에 내장되어있는 substr 함수를 사용하여 문자열의 일부를 집합에 넣는다

 

substr(i, j) : i번째 인덱스부터 j개의 문자를 반환함

 

또한 이중 for문을 이용하여 

겉 for : 몇 개의 문자를 반환할건지 ( 1개 ~ 문자열 길이 )

안 for : 어디 index부터 문자열을 새로 만들건지 ( 0 ~ 문자열 길이 - 1 )

구상했다

 

사실 만들 수 있는 문자열의 개수가 중요한 것이지, 그 안에 있는 문자열이 정렬될 필요는 없다

그래서 시간이 훨씬 빨리 걸리는 unordered_set을 이용하여 중복된 값만 없애주고, 빠르게 동작(시간 복잡도 O(1))하여 최종 문자열의 개수를 출력하였다

 

완성된 코드는 아래와 같다

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

unordered_set<string> myset;
string input;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> input;

	for (int i = 1; i <= input.length(); i++) {
		for (int j = 0; j < input.length(); j++) {
			string temp = "";
			temp = input.substr(j, i);
			myset.insert(temp);
		}
	}

	printf("%d", myset.size());
}