[고급 알고리즘] Dynamic Programming: Palindrome

1. Longest Palindrome Substring (LPS)

• 주어진 문자열의 부분문자열에서 가장 큰 팰린드롬 문자열의 길이 구하기

 

Dynamic Programming

• 시간 복잡도: O(n^2)
• 공간 복잡도: O(n^2)

public static void main(String... args) throws IOException {
    br = new BufferedReader(new InputStreamReader(System.in));
    bw = new BufferedWriter(new OutputStreamWriter(System.out));

    input = br.readLine().toCharArray();
    size = input.length;

    isPalindrome = new boolean[size][size];

    max = 0;

    for (int i = 0; i < size; i++) {
        isPalindrome[i][i] = true;

        if (i+1 < size && input[i] == input[i+1]) isPalindrome[i][i+1] = true;
    }

    for (int radius = 3; radius <= size; radius++) {
        for (int start = 0; start < size; start++) {
            int end = start + radius - 1;
            if (end >= size) break;

            if (input[start] != input[end]) continue;

            isPalindrome[start][end] = isPalindrome[start+1][end-1];

            max = Math.max(max, radius);
        }
    }

    bw.write(max+"");
    bw.flush();
}

 

Manacher's Algorithm 

• 대칭성을 활용하여 중복계산을 줄임
• 모든 팰린드롬을 홀수 길이로 통일

 

• 빠른 성능: O(n)

public static void main(String... args) throws IOException {
    input = br.readLine();
    processedStr = preprocess(input);
    
    size = processedStr.length();
    
    p = new int[size];
    center = centerIdx = right = max = 0;
    
    for (int i = 0; i < size; i++) {
    	int mirror = center * 2 - i;
        
        if (i < right) p[i] = Math.min(right - i, p[mirror];
        
        while (i+p[i]+1 < size && 
               i-p[i]-1 >= 0 && 
               processedStr.charAt(i+p[i]+1) == processedStr.charAt(i-p[i]-1)) p[i]++;
       
       if (i+p[i] > right) {
            center = i;
            right = i + p[i];
       }
       
       if (p[i] > max) {
            max = p[i];
            centerIdx = i;
       }
    }
    
    int start = (centerIndex - max) / 2;
    
    System.out.println(input.substring(start, start + max));
}

public static String preprocess(String s) {
    StringBuilder sb = new StringBuilder();
    sb.append("#");
    
    for (char c : s.toCharArray()) sb.append(c).append("#");
    
    return sb.toString();
}

 

전처리

• 홀수개의 팰린드롬으로 갱신
• 중간에 '#'을 삽입

 

memorization

• 현재까지 가장 먼 팰린드롬 인덱스, 해당 팰린드롬의 중심 인덱스를 기억 (right, center)
• 차례대로 방문하면서 p[i]가 right 범위 내에 있다면, 저장해둔 데이터로 p[i]의 후보군을 지정할 수 있다 (right - i, p[mirror])

 

팰린드롬 확장

• 팰린드롬일 경우, 반지름의 길이를 늘림

 

2. Palindrome Partitioning

• 모든 부분문자열이 팰린드롬이 되도록 나눌 때, 최소한의 조각으로 나누어지는 경우 구하기

 

public static void main(String... args) throws IOException {
    br = new BufferedReader(new InputStreamReader(System.in));
    bw = new BufferedWriter(new OutputStreamWriter(System.out));

    input = br.readLine().toCharArray();
    size = input.length;

    isPalindrome = new boolean[size][size];
    for (int i = 0; i < size; i++) {
        isPalindrome[i][i] = true;

        if (i+1<size && input[i] == input[i+1]) isPalindrome[i][i+1] = true;
    }

    for (int length = 3; length <= size; length++) {
        for (int start = 0; start < size; start++) {
            int end = start + length - 1;
            if (end >= size) break;

            if (input[start] == input[end]) isPalindrome[start][end] = isPalindrome[start+1][end-1];
        }
    }

    dp = new int[size];
    Arrays.fill(dp, Integer.MAX_VALUE);

    for (int end = 0; end < size; end++) {
        for (int start = 0; start <= end; start++) {
            if (!isPalindrome[start][end]) continue;

            dp[end] = start == 0 ? 1 : Math.min(dp[end], dp[start-1] + 1);
        }
    }

    bw.write(dp[size-1]+"");
    bw.flush();

 

3. Palindrome Queries