Manacher 알고리즘

개요 이 알고리즘은 회문(팰린드롬, palindrome)에 관해서 빠른 시간 안에 강력한 솔루션을 제공한다. 여기서 회문이란 $ abcba $처럼 뒤집어서 읽어도 똑같은 문자열을 뜻한다. 여기에 Manacher 알고리즘을 통해 문자열의 모든 위치에 대해서 그 위치를 중심으로 하는 최대 회문의 한쪽 길이를 $ O(n) $안에 구할 수 있다. READ MORE