글 읽기 - 팰린드롬 최소 개수 구하기 문제입니다. 2%에서 틀리는 경우입니다.

spearkkk 6년 전 0

안녕하세요.

제 알고리즘은 다음과 같습니다.

1. 주어진 문자열과 문자열을 뒤집은 문자열(reverse)을 비교합니다.

2. 비교시, 매칭을 시작한 위치와 매칭되는 부분의 합이 전체길이와 같다면 팰린드롬으로 판단합니다.

3. 2번에서 판단한 팰린드롬 부분을 자르고 나머지 문자열에 대해서 반복합니다.

한 예로

anavolimilana이 주어졌을 때, analimilovana 리버스한 문자열을 만들고 비교합니다.

처음 ana가 잘리고

limil, o, v, ana 순으로 잘립니다.

이 알고리즘의 반례가 있을까요?

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

	using namespace std;

	vector<int> getpi(string str) {
		int n = str.size();
		vector<int> pi(n, 0);

		int b = 1;
		int m = 0;

		while (b + m< n) {
			if (str[b + m] == str[m]) {
				++m;
				pi[b + m - 1] = m;
			}
			else {
				if (m == 0) {
					++b;
				}
				else {
					b += m - pi[m - 1];
					m = pi[m - 1];
				}
			}
		}
		return pi;
	}

	int func(string str, string str2) {
		vector<int> pi = getpi(str2);

		int n = str.size();

		if (n == 0) {
			return 0;
		}

		int b = 0;
		int m = 0;

		while (b < n) {
			if (str[b + m] == str2[m] && m < n) {
				++m;
				if (b + m == n) {
					return 1 + func(str.substr(0, b), str2.substr(m));
				}
			}
			else {
				if (m == 0) {
					++b;
				}
				else {
					b += m - pi[m - 1];
					m = pi[m - 1];
				}
			}
		}
	}

	int main() {
		cin.sync_with_stdio(false);

		string str;
		getline(cin, str);

		string re_str = str;
		reverse(re_str.begin(), re_str.end());

		cout << func(str, re_str) << '\n';

		return 0;
	}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

팰린드롬 최소 개수 구하기 문제입니다. 2%에서 틀리는 경우입니다.

spearkkk 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말