팰린드롬 만들기

https://algospot.com/judge/problem/read/PALINDROMIZE

문제설명은 알고스팟에서 참고하세요.

---

팰린드롬 문제를 풀기 위해는 먼저 직전의 알고리즘 게시물인 

http://puppyrush.tistory.com/26

을 이해할 필요가 있습니다.

물론 다른 방법들도 존재하겠지만요.

팰린드롬을 만들기전에 조건인 제일 짧은 팰린드롬을 만들어야 한다에 주안점을 두어야겠습니다.

가령 anon이라는 문자열로 팰린드롬을 만들려 한다면

anon을 뒤집어 연결시킨 anonona도 팰린드롬이 됩니다.

하지만 제일 짧은 팰린드롬은 anona입니다. a하나만 붙은것이죠.

어떻게 하면 짧은 팰린드롬을 만들어낼 수 있을까요

해법중 하나로 원본 문자열을 뒤집어 kmp알고리즘으로 해결하듯이

접근하는것입니다.

0	1	2	3	4	5	6
a	n	o	n
n	o	n	a

다음처럼 원본문자열과 순서가 뒤집힌 문자열을 대조합니다.

맨 처음부터 일치한다면 그 자체가 팰린드롬이겠습니다.

0	1	2	3	4	5	6
a	n	o	n
	n	o	n	a

두 문자열이 겹치는 구간중 모두 일치하면 이때 바로 가장 짧은 팰린드롬을 완성할 수 있습니다.

0	1	2	3	4	5	6
a	n	o	n
			n	o	n	a

물론 이 상황에서도 팰린드롬은 가능하지만 제일 짧은 팰린드롬은 아닙니다.

정리하자면 팰린드롬은 H[m...n] (n=len(H)) 구간과 N[m...n] (m=len(N))이 일치하면 가능합니다.

다시말해 겹치는 두 문자열이 겹치는 구간 중 연속하여 일치하면 된다는 의미입니다.

이를 알고리즘으로 표현하면 위와 같습니다.

kmp알고리즘과 거의 일치하며 팰린드롬 문제를 풀기위해 32,33번줄이 변경된것에 유의하시면 됩니다.

H[m...n] = N[m...n]임을 확인후에 제일 짧은 문자열의 길이를 반환한것입니다.