[algorithm] 팰린드롬 만들기

팰린드롬 만들기

문제

앞에서부터 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 예를 들면 “noon”이나 “stats” 같은 단어들이 팰린드롬입니다. 주어진 문자열 S 뒤에 적절히 문자열을 붙여서 S 를 팰린드롬으로 만들려고 합니다. 예를 들어 S = “anon”이면 뒤에 “ona”를 붙여서 “anonona”를 만들 수도 있고, “a”를 붙여서 “anona”를 만들 수도 있지요. 물론 S를 뒤집은 문자열을 S 뒤에 붙이면 항상 팰린드롬이 되므로, 결과 팰린드롬이 가능한 한 짧았으면 합니다.

S가 주어질 때 S에서 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(<=50)가 주어집니다. 그 후 각 테스트 케이스마다 문자열 S가 주어집니다. 주어지는 문자열의 길이는 1 이상 10만 이하이며, 알파벳 소문자로만 구성됩니다.

출력

각 테스트 케이스마다 한 줄에 S를 이용해 만들 수 있는 가장 짧은 팰린드롬의 길이를 출력합니다.

예제 입력

3

there

amanaplanacanal

xyz

예제 출력

7

21

5

문제 풀이

package algorithm;

 

import java.io.InputStreamReader;

import java.io.BufferedReader;

 

public class Main {

 

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       

        int count = Integer.parseInt(br.readLine());

        for (int i = 0; i < count; i++) {

            solve(br.readLine());

        }

    }

   

    public static void solve(String in) throws Exception {

        String input = in;

        int length = input.length();

        int[] arr = new int[length + 1];

        arr[length] = length;

        arr[length - 1] = length;

        for (int i = length - 2; i >= 0; i--) {

            char c = input.charAt(i);

            int j = arr[i+1];

            while (true) {

                if (c == input.charAt(j-1)) {

                    arr[i] = j-1;

                    break;

                }

                if (j == length) {

                    arr[i] = length;

                    break;

                }

                j = arr[j];

            }

        }

        int j = length;

        for (int i = 0; i < length; i++) {

            char c = input.charAt(i);

            if (c == input.charAt(j-1)) {

                j--;

            } else {

                while (j < length) {

                    j = arr[j];

                    if (c == input.charAt(j-1)) {

                        j--;

                        break;

                    }

                }

            }

        }

        System.out.println(length + j);

    }

}

문제 출처 : 링크