마나커 알고리즘 (Manacher's Algorithm)

O(n) 풀이 - 마나커 알고리즘 | 프로그래머스 스쿨 (programmers.co.kr)

[알고리즘] Manacher’s Algorithm - 마나커(마나허) 알고리즘 : 네이버 블로그 (naver.com)

위에서 자세하게 설명되어 있다.

 

정리

• 기본적으로 한 기준을 중심으로 양옆의 반지름을 계산하므로 홀수의 팰린드롬만 구할 수 있다. 따라서 각 문자 양옆에 특수문자를 추가하여 짝수의 팰린드롬은 특정 위치의 특수문자를 기준으로 팰린드롬으로 구성되도록 만들 수 있다.
• 필요한 변수로는 각 idx에서의 반지름이 있어야 한다. 또한 현재 가장 긴 팰린드롬에서의 끝 idx와 중심 idx를 저장해놔야 한다.
  • 예를 들어 반지름을 d, 끝 idx를 l, 중심 idx를 c라고 했을 때 #a#b#x#b#a의 경우 x위치를 구하기 전에 l은 4, x또한 4이다. 이제 x를 구하면 d는 5이고 l은 9, c는 5이다.
• 핵심 매커니즘으로는 c를 기준으로 대칭을 이룬다는 점이다. 따라서 발생할 수 있는 경우는 총 3가지가 있다.
  • l에 포함된 idx이고 c 좌측에 위치한 대칭점에서의 d값이 우측에 있는 점에 더했을 때도 l에 포함되었을 때이다. 이때는 팰린드롬의 시작 값이 좌측에 위치한 대칭점의 값이다. 이 값 이후의 추가적인 문자가 팰린드롬을 이루는지 보면 된다.
  • l에 포함된 idx이지만 더한 값이 l에 포함되지 않았을 때이다. 이때는 l-idx가 시작값이다.
  • 아예 포함되지 않을 때는 해당 지점부터 팰린드롬을 이루는지 확인해주면 된다.
  • 예시는 아래와 같다.