Boj 9935) 문자열 폭팔

문제

백준 9935

설명

문제를 잘 보면 폭팔 문자열에 중복된 문자가 존재하지 않는다는 걸 볼 수 있다. 이는 곧 폭팔 문자열이 서로 겹쳐서 존재하는 경우가 없다는 것이고, 또한 폭팔에 순서에 따라 결과가 달라지지 않는다는 것이다. 그래서 정답은 여러개가 될 수 없다는걸 확인할 수 있다.

폭팔문자열이 존재하는 경우를 생각해보자. 원래 문자열에 있었거나 문자열이 터진 전후에 생기거나 두가지 경우 뿐이다. 이때 후자의 경우는 원래 터진 문자열의 위치보다 뒤에 존재하게 된다. 그러므로 앞에서부터 탐색하면서 폭팔문자열을 찾으면 지워내는 작업을 하면 된다.

그래서 한꺼번에 넣고 한꺼번에 빼는 스택문제가 되는 것이다.

시간 복잡도

O(\(\mathrm{N}\))

• 탐색할 문자열이 중복 문자를 포함하지 않아서 그냥 선형같은데 정확한지는 잘…

코드

bool Same(string_view a, vector<char>& b)
{
	if (a.size() > b.size()) return false;
	auto ai = a.rbegin();
	auto bi = b.rbegin();
	while (ai != a.rend())
	{
		if (*ai != *bi) return false;
		ai++; bi++;
	}
	return true;
}

int main()
{
	string a; cin >> a;
	string seed; cin >> seed;

	vector<char> s; s.reserve(a.size());
	for (auto c : a)
	{
		s.push_back(c);
		if (Same(seed, s))
			s.erase(s.end() - seed.size(), s.end());
	}
	s.push_back('\0');

	if (s.size() == 1) cout << "FRULA";
	else cout << s.data();
}