# Manacher's algorithm

회문 구하는 알고리즘, 회문이란 좌우가 대칭인 문자열로 짝수, 홀수에 따라 구하는 방식을 다르게 구현하지만 manacher's algorithm을 이용하면 빠른 시간에 회문의 길이를 측정 할 수 있다.

일반적인 회문을 검색하는 방법은 특정 문자를 중심으로 양쪽으로 같은 문자가 있는지 찾는 방식을 취할 수 있다. 해당방식으로 회문을 찾을 경우에는 회문이 짝수 길이를 갖는지, 홀수 길이를 갖는지에 따라 방식을 다르게 구현 할 수 있다.

이러한 방식을 따라 manacher's algorithm을 생각 해 볼 수 있다.

이 알고리즘은 기존에 검색된 회문 정보를 다시 사용하여 검색에 사용합니다. 해당 방식을 간단하게 살펴보려면 일반적인 회문 검색 방식을 살펴볼 필요가 있습니다.

# 회문 검색 방식

중심점을 이동하며 검색을 시작한다. ( 0 <= i < string.length)
중심점 양옆 문자가 같은지 확인한다. (string[i+j] === string[i-j])
양 옆 문자가 같다면 계속해서 진행한다. (j++)
같지 않다면 중심점을 이동한다.
문자열 끝까지 중심점을 이동하며 진행한다.
짝수길이의 회문에 같은 방식으로 검색한다. (j=i 홀수길이 회문 검색 시작점 , j = i+1 짝수길이 회문 검색 시작점)

문자열 전체를 구성하는 회문을 찾는 방식은 다음과 같다.

function solution(s) {
  let start = 0,
    length = 0;
  for (let i = 0; i < s.length; i++) {
    // 전체 문자열 검사
    let left = i,
      right = i; // 홀수 길이 회문 조사
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (length < right - left + 1) {
        start = left;
        length = right - left + 1;
      }
      left--;
      right++;
    }
    left = i;
    right = i + 1; // 짝수 길이 회문 조사
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      if (length < right - left + 1) {
        start = left;
        length = right - left + 1;
      }
      left--;
      right++;
    }
  }
  return s.slice(start, start + length);
}

위와 같은 방식의 회문조사는 각 중심 위치에서 양쪽을 두번에 걸처셔 조사하기 때문에, 최대 시간 복잡도를 O(n^2)을 갖게 된다.

시간 복잡도를 많이 낮출수 있는 manacher's algorithm은 위와 같은 방식에서 기존에 검색된 회문의 정보를 이용하는 방법을 추가하게 된다.

# manacher's algorithm

위의 검색 방식에서 확인한 회문의 정보를 이용하는 방식은 다음과 같은 절차를 따른다.

조사한 회문의 길이가 없다면 기존 회문 조사와 같은 방식을 따른다.
해당 중심점에서 회문의 반지름을 저장한다. (c: 중심, r: 반지름)
중심점 + 반지름을 통해 현재 조사한 위치를 저장한다. ( c+r: 현재 조사된 인덱스)
현재 조사중인 새로운 중심(i)이 가장 최근에 조사된 회문 정보 (c, r)과 어떤 관계인지 확인한다.
- 4-1 현재 중심(i)과 최근 회문 중심(c)의 거리를 구한다. (i-c)
- 4-2 계산된 거리만큼 회문 중심을 기준으로 대칭 이동한다. (j = c - (i-c) = 2*c - i )
- 4-3 대칭점의 회문 길이를 확인한다. (j점의 회문 길이 확인)
- 4-5 j중심의 회문 길이가 r-i보다 큰가 => i점의 회문 길이는 r-i 이다.
- 4-6 j중심의 회문 길이가 r-i보다 작은가 => i점의 회문 길이는 j점의 회문 길이와 같다
- 4-7 j중심의 회문 길이가 r-i와 같은가 => 1번으로 돌아가 다시 시행한다.
관계에 따라 현재 중심(i)에서의 회문을 저장한다.
위와 같은 방법을 문자열 전체를 검사한다.

4-5~7이 되는 이유는 가장 최근에 조사된 회문의 정보를 이용하면 알 수 있다.

모든 정보는 c점을 중심으로 한 회문의 일부라는 점에서 확인할 수 있다.

c점을 중심으로한 회문에 속하는 j,i점은 c점을 중심으로 r만큼 떨어진 거리만큼은 완벽하게 일치한다. 그렇지 않으면 c를 중심으로한 회문의 반지름의 길이가 r이 나타날 수 없기 때문이다.

4-5: j점을 중심으로 하는 회문의 길이가 r-i보다 큰 경우

j를 중심으로 한 회문의 일부가,c를 중심으로한 회문의 반지름인 r을 벗어나는 경우를 생각 해볼 수 있다. 이 경우 i점은 c를 중심으로 r을 벗어나는 경우의 문자가 j점을 중심으로 r을 벗어나는 경우의 문자와 달라졌기 때문에, c를 중심으로 r만큼의 반지름 회문이 발생하게 된다고 볼 수 있다.

이러한 이유로 i를 중심으로 한 회문의 길이는 r-i만큼의 길이를 갖게 된다.

4-6: j점을 중심으로 하는 회문의 길이가 r-i보다 작은 경우

4-5와는 반대로 r-i보다 작은경우는 완벽히 c를 중심으로한 회문에 j를 중심으로한 회문이 속하는 경우로 i를 중심으로한 회문의 길이와 완벽히 같아야 한다.

4-7: j점을 중심으로 하는 회문의 길이가 r-i와 같은 경우

두 개모두 해당하지 않는 경우로 j의 회문의 길이가 정확히 r-i와 같은 경우에는 i의 회문의 길이가 반드시 r-i라는 보장이 없다. c를 중심으로한 c-r-i번째 문자와 c+r+1의 문자가 다른 이유가 i를 중심으로 회문의 x만 큼 떨어진 곳의 문자가 다르다는 뜻은 아니기 때문이다.

이로 인해 i를 기준으로 회문 조사를 다시 진행해야 한다.

이와 같은 방법으로 조사를 진행하면 짝수길이의 회문을 조사할 수 없다. 해당 짝수 길이의 회문을 조사하기 위해서는 문자열 사이사이에 조사에 관여하지 않는 특수 문자 (@, #,등...)을 추가하여 조사를 진행해야 한다.

앞뒤에도 추가하지 않으면 마지막에 오는 반복 짝수문자 검출에 실패하기 때문에 앞뒤에도 해당 특수문자를 추가해야 한다.

var longestPalindrome = function (s) {
  if (s.length === 1) return s;
  let str = ["@", ...s.split("").join("@").split(""), "@"].join("");
  let r = -1,
    p = -1;
  let result = {
    index: 0,
    radius: 0,
  };
  let res = [];

  for (let i = 0; i < str.length; i++) {
    if (r < i) {
      p = r = i;
      while (r < str.length && r <= p * 2 && str[r] === str[2 * p - r]) r++;
      r--;
      res[i] = r - p;
      if (result.radius < r - p) {
        result.index = i;
        result.radius = r - p;
      }
    } else {
      let j = 2 * p - i;
      if (res[j] < r - i) {
        res[i] = res[j];
      } else if (res[j] > r - i) {
        res[i] = r - i;
      } else {
        p = i;
        while (r < str.length && r <= p * 2 && str[r] === str[2 * p - r]) r++;
        r--;
        res[i] = r - p;
        if (result.radius < r - p) {
          result.index = i;
          result.radius = r - p;
        }
      }
    }
  }
  let { index, radius } = result;
  return str.slice(index - radius, index + radius + 1).replaceAll("@", "");
};

두 가지 방식은 공간 복잡도에서 유불리를 다르게 가지고 있으며, 그와 반대인 시간 복잡도 우위를 갖게 된다.

mongoDB →