[Algorithm] Manacher's Algorithm (마나커, 마나허 알고리즘)
Manacher's Algorithm 많은 분이 Palindromic Substring을 찾는 문제 해결 방법을 찾다 Manacher's Algorithm을 알게 됐을텐데, 해당 알고리즘을 알아보겠습니다. Palindrome(회문)이란 순서를 뒤집어도 똑같은 문장 혹은 단어를 의미합니다. race car, noon, 기러기, 다시 합창합시다 등 거꾸로 읽어도 동일한 의미를 가집니다. Core Algorithm 해당 알고리즘은 반복문을 돌며 해당 위치의 문자를 중심으로 Palindrome이 되는지 검사합니다. Brute Force로 생각하면 매 문자를 기준으로 Palindrome이 만족하는지를 반복 검사하면 됩니다. Manacher's Algorithm은 이전에 검사한 Palindrome을 이용해 새로운 Palindrome을 찾는 DP(Dynamic Programming)로 접근합니다. 이를 수행하기 위한 방법인 Mirror Optimization 즉, 대칭점 최적화가 있습니다. Palindrome 특징은 중심을 기준으로 반드시 대칭을 이루는데, 이 특징을 이용하여 이전 Palindrome의 길이를 구해 해당 길이부터 새로운 Palindrome을 찾습니다. 중점 c를 기준으로 aba, aba가 대칭을 이루는 것을 볼 수 있습니다. 위 대칭점을 찾을 때 반드시 최적화 과정이 필요한데, 왜 최적화 과정이 필요한지 알아보겠습니다. Algorithm 조건 1 대칭점을 찾기 전, 필요한 변수는 총 3개 입니다. Palindrome의 중심값 Center Palindrome의 오른쪽 끝 위치값 Right i번째 Palindrome의 길이를 저장하는 P 리스트 (C부터 R의 반지름 크기 저장) 이후 i번째 인덱스의 대칭점(mirror)을 찾기 위해 mirror = C*2-i 공식을 이용해 대칭점을 찾고 이를 최적화합니다. 결론적으로 이와 같은 수식이...