Manacher 알고리즘

 

❐ Description

---

[5. Longest Palindromic Substring] 문제를 풀면서 알게 된 Manacher 알고리즘 정리. 

 

 

 

 

 

 

❐ Manacher 알고리즘 이해하기

---

Manacher 알고리즘은 문자열에서 가장 긴 팰린드롬 부분 문자열을 효율적으로 찾는 알고리즘이다.

일반적인 방법으로 풀 경우 O(n²)의 시간 복잡도가 걸리지만, Manacher 알고리즘은 이를 O(n)으로 줄여준다.

이 알고리즘은 팰린드롬의 대칭성을 이용하여 중복 계산을 줄이는 방식(동적 프로그래밍)으로 동작한다.

 

 

코드로 이해해 보았다. 

다른 블로그들은 변수명이 엉망 그 자체다...

변수명	의미
radiuses	반지름 배열
currentCenterIdx	탐색 과정에서 수시로 변경되는 중심 인덱스
centerIdxOfMaxPalindrome	현재까지 찾은 가장 긴 팰린드롬의 중심 인덱스
rightBoundary	현재까지 찾은 가장 긴 팰린드롬의 오른쪽 가장 끝 인덱스
mirrorIdx	currentCenterIdx를 기준으로 현재 탐색하고 있는 요소(i)의 대칭되는 요소의 인덱스

 

public String longestPalindrome(String s) {
    // 1. 문자열 변환
    StringBuilder builder = new StringBuilder();
    builder.append("#");
    for (char c : s.toCharArray()) {
        builder.append(c).append("#");
    }
    String transformedInput = builder.toString();

    // 2. 변수 초기화
    int inputLen = transformedInput.length();
    int[] radiuses = new int[inputLen]; // 팰린드롬 반지름 배열
    int currentCenterIdx = 0, rightBoundary = 0; // 중심과 오른쪽 경계
    int maxLen = 0, centerIdxOfMaxPalindrome = 0;

    // 3. radiuses 배열 계산
    for (int i = 0; i < inputLen; i++) {
        int mirrorIdx = 2 * currentCenterIdx - i; // i의 거울 위치
        if (i < rightBoundary) {
            radiuses[i] = Math.min(rightBoundary - i, radiuses[mirrorIdx]);
        }

        // 4. 팰린드롬 확장
        while (i + radiuses[i] + 1 < inputLen && i - (radiuses[i] + 1) >= 0 &&
                transformedInput.charAt(i + radiuses[i] + 1) == transformedInput.charAt(i - (radiuses[i] + 1))) {
            radiuses[i]++;
        }

        // 5. 중심과 오른쪽 경계 업데이트
        if (i + radiuses[i] > rightBoundary) {
            currentCenterIdx = i;
            rightBoundary = i + radiuses[i];
        }

        // 6. 최대 길이 갱신
        if (radiuses[i] > maxLen) {
            maxLen = radiuses[i];
            centerIdxOfMaxPalindrome = i;
        }
    }

    // 7. 결과 추출
    int start = (centerIdxOfMaxPalindrome - maxLen) / 2; // 원본 문자열에서 시작 위치
    return s.substring(start, start + maxLen);
}

 

1. 홀수 길이와 짝수 길이를 동일하게 다룰 수 있도록 하기 위해서 임의의 문자열(#) 추가

StringBuilder builder = new StringBuilder();
builder.append("#");
for (char c : s.toCharArray()) {
    builder.append(c).append("#");
}
String transformedInput = builder.toString();

 

 

2. 변수 초기화

int inputLen = transformedInput.length();
int[] radiuses = new int[inputLen];
int currentCenterIdx = 0, rightBoundary = 0;
int maxLen = 0, centerIdxOfMaxPalindrome = 0;

 

 

3. radiuses 배열 계산

3번 과정에서 많은 subtask들이 수행된다.

 

3-1. 현재 탐색 중인 요소(i)의 대칭 인덱스 찾기

int mirrorIdx = 2 * currentCenterIdx - i;

 

 

3-2. 현재 탐색 중인 요소(i)가 rightBoundary 내에 있다면 대칭성을 이용하기

if (i < rightBoundary) {
    radiuses[i] = Math.min(rightBoundary - i, radiuses[mirrorIdx]);
}

• `rightBoundary - 1` : 현재까지 찾은 가장 긴 palindrome의 오른쪽 끝까지의 거리

 

3-3. Palindrome 확장

// i + radiuses[i] + 1 : 현재 중심 기준 왼쪽 문자 idx
// i - (radiuses[i] + 1) : 현재 중심 기준 왼쪽 문자 idx
while (i + radiuses[i] + 1 < inputLen && i - radiuses[i] - 1 >= 0 &&
        transformedInput.charAt(i + radiuses[i] + 1) == transformedInput.charAt(i - radiuses[i] - 1)) {
    radiuses[i]++;
}

 

 

3-4. 현재 중심과 rightBoundary(오른쪽 경계) 갱신

if (i + radiuses[i] > rightBoundary) {
    currentCenterIdx = i;
    rightBoundary = i + radiuses[i];
}

 

 

3-5. 최대 길이의 Palindrome 길이 갱신

if (radiuses[i] > maxLen) {
    maxLen = radiuses[i];
    centerIdxOfMaxPalindrome = i;
}

 

 

3-6. 결과 추출

int start = (centerIdxOfMaxPalindrome - maxLen) / 2;
return s.substring(start, start + maxLen);

• `(centerIdxOfMaxPalindrome - maxLen) / 2` : 원본 문자열에서 시작 위치를 구하기 위함.

 

 

 

 

 

---