Manacher's 알고리즘(팰린드롬, 회문)

코딩 테스트 문제 중에서 팰린드롬인지 체크하고 아니면 문자열을 붙여서 최소길이의 팰린드롬을 만드는 문제였다.

비슷한 백준 사이트의 팰린드롬 문제
프로그래머스 가장 긴 팰린드롬
팰린드롬이란?
abba, madam과 같이 거꾸로 읽어도 같은 문자열.

참고 유튜브

    public static int solution(String s)
    {
        int answer = 0;

        String tmp = "";
        tmp += "$";
        for(int i=0; i<s.length(); i++)
        {
            tmp += "#";
            tmp += s.charAt(i);
        }
        tmp+="#@";
        System.out.println(tmp);
        //문자 양끝에 $,@를 붙이고 문자 사이마다 #을 넣어줌.


        int[] P = new int[tmp.length()]; //팰린드롬 길이를 저장할 배열.
        int C =0, R =0;

        for(int i=1; i<tmp.length()-1; i++)
        {
            int mirr = 2*C - i;

            if(i<R)
                P[i] = Math.min(R-i, P[mirr]);

            while(tmp.charAt(i+(1+P[i]))==tmp.charAt(i-(1+P[i])))
                P[i]++;

            if(i+P[i]>R){
                C = i;
                R = i + P[i];
            }
        }

        for(int i=0; i<P.length; i++)
        {
           answer = Math.max(answer, P[i]);
        }



        return answer;
    }