글 읽기 - 팰린드롬 최소개수 구하기.

lyzqm 6년 전 0

manacher 알고리즘써서 짝수일경우를 대비해서 '#'을 사이사이에 껴주어서 풀었는데 틀린곳을 못찾겠네요..

abba 6

abcbad 8

aaa 6

aaaa 10

도와주세요 ㅠㅠ

#include <cstdio>
#define min(a,b) ((a<b)?a:b)
int main(){
	int len = 0;
	char input[32], str[64] = "";
	scanf("%s", input);

	for (len = 0; input[len]; len++);
	len = len * 2 + 1;
	for (int l = 0; l < len; l++){
		if (l & 1) str[l] = input[(l - 1) / 2];
		else str[l] = '#';
	}

	//manacher algorithm
	int A[64];
	int R = -1, P = -1;
	int ans = 0;

	for (int n = 0; n < len; n++){
		printf("%c", str[n]);
		if (n <= R) A[n] = min(A[2 * P - n], R - n);
		else A[n] = 0;
		while (str[n - A[n] - 1] == str[n + A[n] + 1])
			A[n] = A[n] + 1;
		if (n + A[n] > R){
			R = n + A[n];
			P = n;
		}
	}
	printf("\n");
	for (int n = 0; n < len; n++){
		printf("%d", A[n]);
		ans += (A[n] + 1) / 2;
	}
	printf("\n%d\n", ans);
	return 0;
}

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

문제

문제

출처

ICPC

팰린드롬 최소개수 구하기.

lyzqm 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말