Manacher's Algorithm
부분 문자열이 팰린드롬인지를 판단하려면 보통 O(n^2) 의 시간복잡도가 필요하다.
Manacher's Algorithm 은 부분 문자열의 팰린드롬 판단을 O(n) 에 가능하도록 한다.
코드
https://www.acmicpc.net/problem/14444 문제에 대한 풀이
정리
- 문자열에 대한 배열 A를 구한다. 배열 A의 정의는 아래와 같다
- A[i] : i번째 문자의 최대 회문 반지름 길이
- 예를들어 bananas 에서 A[3] 은 anana 이므로 2이다.
- Manacher's Algorithm
- i는 1...n 으로 진행한다
- j < i 인 모든 j에 대하여, r = max(j + A[j]) 이라 할 때, r이 최대 값일 때 j를 p라 하자.
- i와 r의 대소관계에 따라 A[i]를 구할 수 있다.
- i >= r, A[i] = 0 (초기값)
- i <= r, i는 p를 중심으로한 회문이다.
- 작성중..