[백준] 11478 서로 다른 부분 문자열의 개수 with C++

문제설명

---

입출력 예제

---

개념

　문자열 S에 대해 서로 다른 부분 문자열의 개수를 구하는 문제다. 여기서 연속된 일부분이라는 것에 주목해야 한다. 즉,

• S의 길이가 1인 부분 문자열은 a, b, a, b, c가 되고, 여기서 서로 다른 부분 문자열은 a, b, c
• S의 길이가 2인 부분 문자열은 ab, ba, ab, bc가 되고, 여기서 서로 다른 부분 문자열은 ab, ba, bc
• S의 길이가 3인 부분 문자열은 aba, bab, abc가 되고, 여기서 서로 다른 부분 문자열은 aba, bab, abc
• S의 길이가 4인 부분 문자열은 abab, babc가 되고, 여기서 서로 다른 부분 문자열은 abab, babc
• S의 길이가 5인 부분 문자열은 ababc가 되고, 여기서 서로 다른 부분 문자열은 ababc

　따라서 반복문을 이용해 길이가 i일 때, 문자열을 substr을 이용해 자르고 중복된 것은 지워주면 된다.

---

풀이

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

int main()
{
	std::string str;
	std::cin >> str;
	int count = 0;

　문자열 str를 초기화하고, 서로 다른 부분 문자열의 개수를 저장할 count를 0으로 초기화한다.

 

	for (int i = 0; i < str.size(); i++)
	{
		std::vector<std::string> v;

		for (int j = 0; j < str.size() - i; j++)
		{
			std::string tmp = str.substr(j, 1 + i);
			v.push_back(tmp);
		}
		
		std::sort(v.begin(), v.end());
		v.erase(std::unique(v.begin(), v.end()), v.end());
		count += v.size();
	}

	std::cout << count;
}

　string을 담는 벡터 v를 매 반복마다 초기화해 준다. 그리고 문자열의 길이를 잘라서 벡터에 삽입한 뒤, 중복된 원소를 제거해 준다. 마지막으로 정렬된 벡터의 크기를 count 변수에 계속 더해주면 된다.

 

총합본

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

int main()
{
	std::string str;
	std::cin >> str;
	int count = 0;

	for (int i = 0; i < str.size(); i++)
	{
		std::vector<std::string> v;

		for (int j = 0; j < str.size() - i; j++)
		{
			std::string tmp = str.substr(j, 1 + i);
			v.push_back(tmp);
		}
		
		std::sort(v.begin(), v.end());
		v.erase(std::unique(v.begin(), v.end()), v.end());
		count += v.size();
	}

	std::cout << count;
}