BOJ 1254 팰린드롬 만들기

어떤 문자열이 주어지면 그 문자열 뒤에 0개 이상의 문자를 추가해서 팰린드롬을 만들되, 가능하면 짧게 만들어야하는 문제이다. 가장 짧은 팰린드롬의 길이를 출력하는 문제인데,

일단 문자열 뒤에 문자를 추가할 때는 문자열을 구성하는 문자 중 가장 앞의 문자부터 추가해야 한다. 왜냐하면 팰린드롬이려면 0번째와 n-1번째, 1번째와 n-2번째, ... 이렇게 앞 뒤 문자가 같아야 되는데, 주어진 문자열 자체로 팰린드롬이 아니고 최소 개수의 문자를 추가해서 팰린드롬을 만들어야 한다면 ...
abcd가 있다고 하자. 그럼 일단 a부터 붙여본다. abcda 하지만 b와 d가 달라서 실패.
그 다음에는 뭘 붙여봐야할까? 바로 ba를 붙여본다. 그래도 아니면 그 다음에는? cba..
물론, abcd를 거꾸로 한 dcba를 붙이면 당연히 팰린드롬이 되겠지만 이 문제에서는 최소 길이를 구해야 하므로 이렇게 작은 경우부터 붙여보면서 이게 팰린드롬인지 아닌지 검사해보는 방법이 있다. 이 문제에서는 n이 작기 때문에 n가지 경우의 문자열을 만들고 일일이 팰린드롬인지 아닌지 검사하면 O(N*2N)  즉, O(N^2)에 될 것이다.

=>*** 이 방법으로 구현하고, 고수님들의 코드를 봤는데... 굳이 저렇게 모든 경우를 만들어 볼 필요가 없다!! 뒤에 붙여서 팰린드롬이 되려면, 원래 문자열에서 그 붙이는 만큼의 prefix를 제외한 나머지 문자열이 팰린드롬이 되어야 한다! 그렇기 때문에 원래 문자열의 suffix를 검사해보면서 팰린드롬이 되면 원래 문자열에서 그 suffix만큼의 길이를 빼준 만큼만 뒤에 덧 붙여주면 된다는 것이다....!! 아... 엄청난 것 같다. 이렇게 간단하다니... 이 방법으로도 풀어서 제출해야 겠다.

또 한가지 방법은 JM book 문자열 부분에 나온 방법인데, 어떤 문자열S가 있으면 그 문자열을 뒤집은 RS를 만든 후, S의 suffix와 RS의 prefix를 비교해서 공통이면서 가장 긴 부분을 찾는다. 즉 S의 뒷부분과 RS의 앞부분이 최대한 겹치면 그 것이 가장 짧은 팰린드롬이 된다. 그렇기 때문에 kmp를 이용해서 겹치는 부분의 최대 길이를 구하고 그 값을 원래 문자열의 길이에서 뺀 만큼만 원래 문자열에 추가해주면 최소 길이를 구할 수 있다.
아무래도 이 방법은 O(N)만에 될 것 같다.

위의 3가지 방법으로 모두 AC를 받았다.