manacher's algorithm 썸네일형 리스트형 BOJ)11046 팰린드롬?? 문제: icpc.me/11046 길이가 최대 100만인 문자열 s가 주어질 때 s의 인덱스 l~r 까지의 부분 문자열이 팰린드롬인지 쿼리마다 출력하는 문제이다. n이 작다면 n^2의 방법으로 해결해줄 수 있지만 n이 크므로 manacher's 알고리즘을 이용하여 해결해주어야 한다. manacher's 알고리즘으로 전처리를 해준 뒤 중심으로 부터의 최대 팰린드롬 길이와 주어진 구간의 길이를 비교해주어 답을 출력해주면 된다. 시간 복잡도는 O(N+M)이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include #include #include using.. 더보기 이전 1 다음