팰린드롬 (APIO 2014)

http://geniusainta.com/problems/view/APIO14_palindrome

이 문제의 정해는 Manacher's Algorithm + Suffix Array이다.

난 전자는 알지만 후자는 모르기 때문에 (...) SA 대신 Hash를 사용해서 풀었다. 때문에 처음부터 해시를 사용했다는 가정 하에 설명한다. 

unordered_map을 기준으로 설명한다 (괜히 로그떼면 기분 좋으니까 (?))

1. Naive - O(n^2)

substring의 개수가 O(n^2)이며 해싱을 사용하면 팰린드롬 판별은 O(1)에 가능하다. 모든 팰린드롬을 map에 때려박고 개수를 세면 된다.

2. Hash + Manacher + Tree - O(n)

일단 한 문자열의 서로 다른 팰린드롬의 개수는 n개임을 알고 있어야 한다.

난 이말을 어디서 들었고 (...) 이해는 나중에 했다. 이를 보이려면 Manacher's algorithm이 돌아가는 과정과 시간 복잡도가 O(n) 인 이유를 이해하고 있어야 한다. [1] [2]

대강 증명하자면, Manacher's Algorithm에서는 초기에 두가지 선택지를 준다.

 * 이미 있던 DP값을 불러서 쓰거나

 * DP값이 너무 길기에, 짤라서 쓰거나

이 중 전자의 경우에는 확장이 일어나지 않으며, 후자의 경우에만 확장이 일어난다. 확장이 일어난다는 것은 Max(i + DP[i]) 의 값이 증가한다는 것을 의미하며, 이러한 증가는 많아야 n번 일어나기 때문에 시간 복잡도가 O(n)이다.

마찬가지로, 확장이 일어나지 않을때는 새로운 팰린드롬이 생기지 않으며, 확장이 일어날 때만 새로운 팰린드롬이 1개씩 생긴다. (확장하는 구간을 모두 포함하는 큰 팰린드롬이 확장 과정에서 생긴 유일한 팰린드롬이다.) 때문에 서로 다른 팰린드롬의 개수 역시 n개일 것이다.

이로써 카운트 해야할 팰린드롬의 수가 n개임을 보였으니 n개의 팰린드롬이 등장하는 횟수를 빠르게 셀 수 있으면 되는데, 이 과정에서 트리를 사용할 수가 있다.

먼저 Manacher's Algorithm을 사용해서 해당 구간을 중심으로 하는 가장 넓은 팰린드롬을 모두 구한 후, 각 팰린드롬을 서서히 좁혀가면서 트리를 만든다. ([s,e] -> [s+1,e-1] -> [s+2,e-2] ....) 이 때 [s,e] hash의 parent는 [s+1,e-1] 이라고 정의한다. 이렇게 해서, 현재 트리에 이미 존재하는 해시값이 나올때까지 이 연산을 반복한다. 팰린드롬이 n개기 때문에  트리의 정점이 n개임은 자명하다.

이 과정을 naive하게 하면 [s,e] 의 모든 parent의 count값을 1씩 더하면서 풀 수 있는데, 이를 뒤집어서 생각해 보면, 어떤 정점을 루트로 하는 서브트리에서, 구간에서 가장 긴 팰린드롬의 개수를 세는 방식으로도 충분히 문제를 풀 수 있다.

때문에 처음 트리를 만들때 [s,e] 정점의 카운트를 늘린 후, dfs로 간단히 서브트리의 카운트를 모두 센 후 갱신해주면, 한번의 DFS로 최댓값을 구할 수 있다.

여담으로 Anti-hash test case가 있기 때문에 해시 base를 2개 만들어놓고 mod p로 계산하는 것을 추천한다.