알고리즘에서 '매나커(Manacher) 알고리즘'의 용도는?

해설

매나커 알고리즘은 각 위치를 중심으로 하는 최장 회문의 반지름을 O(n) 시간에 모두 구합니다. 이전에 계산한 회문 정보를 활용하여 중복 비교를 줄이는 것이 핵심입니다. 나이브 접근의 O(n²)보다 크게 효율적이며, 최장 회문 부분 문자열 문제에 활용됩니다.