gaki gaki

안녕하세요. gaki 입니다. 오늘은 가장 긴 펠렌드롬을 O(N) 의 시간복잡도로 찾을 수 있는 Manacher's 알고리즘에 대해서 이야기 해보겠습니다. 1. O(N^2) 으로 가장 긴 펠렌드롬 찾는 방법 2. Manacher's 알고리즘의 접근 방법 3. LeetCode 문제풀이 1. O(N^2) 으로 가장 긴 펠린드롬을 찾는 방법 먼저 Manacher's 알고리즘에 대해서 알아보기 전에, 이 알고리즘이 왜 유용한지에 대해서 설명해보겠습니다. babad 위와 같은 문자열이 있다고 가정해봅시다. 이 문자열에서 가장 긴 펠렌드롬을 찾으려면 어떻게 해야할까요? 아니, 그 전에 펠렌드롬이 뭔지 알아야겠죠? 펠렌드롬은 거꾸로 뒤집어도 원래의 문자열과 같은 문자열을 의미합니다. 가령, ABBCBBA 라는 문자열..