Manacher 알고리즘

2024. 12. 15. 22:11·Algorithm/내용 정리

 

❐ 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` : 원본 문자열에서 시작 위치를 구하기 위함.

 

 

 

 

 


'Algorithm > 내용 정리' 카테고리의 다른 글

Memoization (메모이제이션)  (0) 2025.01.09
Binary Search는 꼭 정렬된 배열에서만 사용해야 할까?  (0) 2025.01.06
Back Tracking  (0) 2024.11.20
Binary Search  (0) 2024.10.01
Dutch National Flag  (0) 2024.10.01
'Algorithm/내용 정리' 카테고리의 다른 글
  • Memoization (메모이제이션)
  • Binary Search는 꼭 정렬된 배열에서만 사용해야 할까?
  • Back Tracking
  • Binary Search
gilbert9172
gilbert9172
gilbert9172 님의 블로그 입니다.
  • gilbert9172
    バックエンド
    gilbert9172
  • 전체
    오늘
    어제
    • All Categories (166)
      • 우테코 7기 (21)
        • 1주차 (8)
        • 2주차 (5)
        • 3주차 (6)
      • Langauge (4)
        • Java (3)
        • Kotlin (1)
      • Back-End (13)
        • SpringBoot (1)
        • Trouble Shooting (0)
        • Setup & Configuration (1)
        • SQL (3)
        • Redis (8)
      • Architecture (6)
        • Multi Module (1)
        • DDD (5)
      • CS (30)
        • Data Structure (6)
        • Operating System (0)
        • Network (12)
        • Database (10)
        • Design Pattern (2)
      • Algorithm (78)
        • 내용 정리 (18)
        • 문제풀이 (60)
      • DevOps (6)
        • AWS (5)
        • Git (1)
      • Front-End (1)
        • Trouble Shooting (1)
      • Project (6)
        • 페이스콕 (6)
      • Book (0)
        • 마스터링 블록체인 (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    오블완
    부분단조성
    Two-Pointer
    Back-Tracking
    greedy
    sliding-window
    binarysearch
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.2
gilbert9172
Manacher 알고리즘
상단으로

티스토리툴바