[Leetcode] 5. Longest Palindromic Substring

주어진 문자열에서 가장 긴 회문을 찾아내는 문제. 마나커 알고리즘을 사용하면 O(N) 으로 해결이 가능하다.

마나커 알고리즘

일반적으로 문자열의 모든 부분 문자열을 확인하여 회문인지 판별하면 O(N^3)의 시간이 걸린다. 문자열의 중심을 기준으로 좌우 확장하더라도 O(N^2) 이다. 하지만 마나커 알고리즘은 O(N) 에 해결이 가능하다.

이는 이미 찾은 회문의 대칭되는 부분의 값을 가져와서 사용하기 때문에 가능하다. 가장 긴 회문의 중심과 제일 오른쪽 인덱스를 저장하고 있기 때문에 탐색이 진행될 수록 거울상을 그리는 부분에 회문이 존재한다면 현재 위치에도 존재함을 알 수 있기 때문이다.

먼저 문자열을 쪼개고 양쪽에 특수문자를 넣어 문자열이 항상 홀수가 됨을 보장한다. 이후 차례대로 인덱스 i 를 증가시키며 해당 인덱스를 중심으로 좌우에 같은 값들이 있는지 확인해나간다. 그리고 right 보다 i가 작다면(현재 위치가 이미 확인된 회문의 내부라면) center 를 기준으로 거울상을 그리는 위치의 회문 정보를 찾아와 초기값으로 사용한다. 따라서 i + P[i] 이후의 위치만 보면 된다.

전체 연산 횟수는 대략적으로 2*N 이므로 O(N) 이라 볼 수 있다.

function longestPalindrome(s: string): string {
    if (s.length === 1) {
        return s
    }

    const T = '#' + s.split('').join('#') + '#';

    const P = Array.from({ length: T.length }, () => 0);


    let center = 0;
    let right = 0;

    for (let i = 0; i < T.length; i++) {
        let iMirror = 2 * center - i;

        if (right > i) {
            P[i] = Math.min(right - i, P[iMirror])
        } else {
            P[i] = 0;
        }

        while (
            i - 1 - P[i] >= 0 &&
            i + 1 + P[i] < P.length &&
            T[i - 1 - P[i]] === T[i + 1 + P[i]]
        ) {
            P[i] += 1;
        }

        if (P[i] + i > right) {
            right = P[i] + i;
            center = i;
        }
    }

    let maxLength = 0;
    let centerIndex = 0;

    for (let i = 0; i < P.length; i++) {
        if (P[i] > maxLength) {
            maxLength = P[i];
            centerIndex = i;
        }
    }

    const startIndex = (centerIndex - maxLength) / 2;

    const answer = s.slice(startIndex, startIndex + maxLength)
    return answer;
};