알고리즘/문자열
2021. 2. 5.
Manacher
길이가 \(n\)인 문자열 \(S\)가 있습니다. 이 문자열의 부분 문자열 중 팰린드롬인 것을 모두 알고 싶다면, 어떻게 하면 될까요? 나이브하게 \(O(n^3)\) 또는 \(O(n^2)\)로도 해결할 수 있겠지만, 이를 \(O(n)\)에 해결할 수 있는 Manacher 알고리즘에 대해 알아봅시다. \(S\)의 각 \(i\)번째 문자를 중심으로 하는 팰린드롬의 최대 반지름을 \(A_i\)라고 정의합시다. 또, \(j m\) 현재 얻을 수 있..