manacher 응용문제로 이해력 높이기 - 회문인 부분문자열의 개수를 찾는법

1. 문제 16163번: #15164번_제보 (acmicpc.net) 16163번: #15164번_제보 www.acmicpc.net 2. 풀이 연속인 부분문자열에서 회문의 개수를 구하는 문제 manacher 알고리즘을 수행하면서, 나타나는 회문의 개수를 세면 될 것이다... 그런데 회문의 개수를 어떻게 세야할까 예를 들어 ABCBA에 대해서.. manacher 알고리즘을 수행하기 위해 #을 붙여가지고 #A#B#C#B#A#으로 바꾸고 나서.. 각 index에 대해서 양쪽으로 확대해나가 회문인지 찾아나갈텐데 A배열은 각 위치에서 가장 긴 회문의 반지름 길이를 나타내는 것으로, 가장 긴 회문의 반지름 길이를 알고 있다면, 이는 그보다 작은 회문도 포함하고 있는거니까, 이 값을 이용한다면 해당 지점에서 회문의 ..