https://medium.com/@alessiopiergiacomi/eertree-or-palindromic-tree-82453e75025b 와 Rubinchik, M., & Shur, A. M. (2016). EERTREE: An Efficient Data Structure for Processing Palindromes in Strings. 를 참고하여 작성한 글임을 밝힙니다.
Intro
ICPC 등의 알고리즘 경진 대회에는 문자열을 다루는 종류의 문제가 자주 출제됩니다. 이런 문자열 문제들을 풀다 보면, 특수한 문자열에 대한 깊은 고찰을 요구하는 상황들이 많이 등장합니다. 이런 특수한 문자열 중 팰린드롬은 오래 전부터 깊은 연구가 진행되어 왔고, 팰린드롬의 성질을 이용하여 관련 문제를 효율적으로 해결하는 다양한 알고리즘이 개발되었습니다. 대표적인 예시로 길이 $ n $인 문자열 $ S $의 최장 길이 팰린드롬을 $ O(n) $ 시간만에 구하는 Manacher’s Algorithm 이 있습니다.
본 글에서 설명할 eertree (Palindromic Tree)는 팰린드롬을 효율적으로 저장하는 자료구조입니다.
Terms
본 글에서 문자열은 $ S[1…n] $ 로 나타내기로 합니다. 별다른 언급이 없으면 $ S $와 같은 표기는 $ S[1…n] $과 동일한 의미를 가집니다. $ S[i] $는 문자열 $ S $의 $ i $번째 문자를 나타냅니다.
문자열 $ S $가 팰린드롬 (Palindrome) 인 것은 모든 $ 1 \leq i \leq n $ 에 대해 $ S[i] = S[n+1-i] $ 가 성립한다는 것과 동치입니다. 이때 길이가 0인 문자열 또한 팰린드롬으로 봅니다.
$ 1 \leq i \leq j \leq n $ 에 대해 $ T = S[i…j] $ 로 나타내어지는 문자열 $ T $를 $ S $의 부분 문자열 (Substring) 이라고 합니다. 여기서 $ j = n $ 인 경우 $ T $를 $ S $의 접미사 (Suffix) 라고 부릅니다. 일반적으로 $ S $는 $ S $의 suffix이지만, 본 글에서 “$ S $의 가장 긴 팰린드롬 suffix” 를 칭할 때에는 $ S $ 본인이 팰린드롬인 경우는 제외하고 생각합니다.
Motivation
어떤 문자열 $ S $ 의 서로 다른 팰린드롬의 개수를 구하는 문제를 생각해봅시다.
$ S $의 가능한 substring의 개수가 $ \Theta(n^2) $ 개이기 때문에 서로 다른 팰린드롬도 $ \Theta(n^2) $ 개 존재할 것이라고 추측하고, 실제로 서로 다른 팰린드롬이 $ \Theta(n^2) $ 개인 문자열을 잡아보려고 하면 생각보다 쉽게 되지 않음을 알 수 있습니다. “aaaaaaaa”와 같이 모든 substring이 팰린드롬인 문자열을 생각해도 서로 겹치는 것이 많아 최종적으로 서로 다른 팰린드롬의 수는 $ O(n) $이 됩니다. “abababa”, “abcbabcba” 와 같은 문자열을 잡아도 이는 마찬가지입니다.
실제로, $ S $에 존재하는 서로 다른 팰린드롬은 많아야 $ n $개라는 사실을 증명할 수 있습니다. 증명은 다음과 같은 귀납적인 과정을 통해서 이루어집니다.
- 길이가 1인 문자열의 경우, 전체 문자열이 유일하게 존재하는 팰린드롬이므로 위의 성질이 성립합니다.
- 길이가 $ n-1 $인 문자열 $ S[1…n-1] $ 의 서로 다른 팰린드롬의 수가 $ n-1 $개 이하라고 가정합시다. 이 문자열에 $ n $번째 문자를 추가했을 때, $ S[n] $ 을 끝으로 하면서, $ S[1…n-1] $에 등장하지 않은 팰린드롬이 많아야 1개 존재하면 귀납법으로 문제를 증명할 수 있습니다.
- 만약 그러한 팰린드롬이 두 개 존재한다고 하고, $ i<j $ 에 대해 $ S[i…n] $ 과 $ S[j…n] $ 이라고 합시다. 이때 $ S[j…n] $ 은 $ S[i…n] $ 의 부분 문자열이 됩니다. $ S[i…n] $ 이 팰린드롬이므로, $ S[j…n] $ 을 $ S[i…n] $ 상에서 “뒤집은” 문자열, 즉 $ S[i…i+n-j+1] $ 은 $ S[j…n] $ 과 정확히 같은 문자열이 됩니다. 즉 $ S[j…n] $ 과 같은 팰린드롬이 $ S[n] $ 이 문자열에 추가되기 전에 등장했으므로 모순이 발생합니다.
- 따라서 문자열에 문자 하나를 추가하는 과정에서 새로 생기는 팰린드롬은 최대 1개이므로 $ S[1…n] $ 에 속하는 서로 다른 팰린드롬은 많아야 $ n $개입니다.
위 증명이 시사하는 바는, 문자열 $ S $에 새로운 문자 $ c $ 를 끝에 추가할 때 새로 추가되는 팰린드롬의 수는 최대 1개이며, 그것의 유일한 후보는 $ Sc$ 의 가장 긴 팰린드롬 suffix라는 것입니다. 그런 문자열은 $ S $의 팰린드롬 suffix $ T $에 대 $ cTc$ 꼴로 나타내어질 것이므로, 우리가 모든 $ T $에 대한 정보를 가지고 있다면 모든 $ T $를 보면서 $ Sc $ 의 팰린드롬 suffix에 대한 정보를 구할 수 있겠네요. 즉, 문자를 하나씩 추가하면서 팰린드롬 suffix에 대한 정보를 관리한다면 이 문제를 해결할 수 있습니다.
eertree는 이 과정을 문자열의 길이에 비례하는 시간에 관리하는 자료구조입니다.
edge와 suffix link
길이가 $ n (\geq 2) $ 인 팰린드롬의 처음과 마지막 문자를 제거하면 길이가 $ n-2 $ 인 팰린드롬이 됩니다. 즉 한 문자열에 등장하는 여러 팰린드롬 사이에는 서로 포함하는 관계가 존재하고, 이런 관계는 트리 구조로 나타낼 수 있습니다. 구체적으로, 각 팰린드롬에 대응하는 정점을 가진 그래프에서 두 팰린드롬 $ S $와 $ T $가 $ S $ = $ cTc $ 인 관계를 가질 때 $ c $로 라벨링된 $ T \rightarrow S $ 간선을 준다면, 이 그래프는 여러 독립적인 트리의 집합인 포레스트를 이루게 됩니다. eertree는 이 구조를 기반으로 설계된 자료구조이며, 여기서 정의된 간선을 edge 라고 부르기로 합니다.
보통은 구현 및 설명의 편의성을 위해, 이 구조에 길이 0인 팰린드롬과 길이 -1인 팰린드롬을 나타내는 가상의 정점 $ O $와 $ I $를 추가적으로 정의합니다. $ O $에서 모든 길이 2인 팰린드롬으로 가는 edge를 주고, $ I $에서 모든 길이 1인 팰린드롬으로 가는 edge를 주고, $ I $에서 $ O $로 가는 edge를 주면 전체 그래프가 $ I $를 루트로 하는 하나의 트리로 묶이게 됩니다.
Motivation에서 살펴보았듯이, 이런 구조를 유지하기 위해서는 문자열의 팰린드롬 suffix에 대한 정보를 관리하는 것이 중요합니다. 따라서 eertree에는 팰린드롬 사이의 포함 관계를 나타내는 edge 외에도 suffix link 라고 부르는 방향 간선이 존재합니다. 모든 정점에 대해, 해당 정점을 나타내는 팰린드롬 $ S $ 의 suffix중 가장 긴 팰린드롬을 $ T $라고 할 때 $ S \rightarrow T $ 인 suffix link가 존재하고, $ suf(S) = T $ 라는 표기를 사용합니다. $ suf(O) = suf(I) = I $ 로 정의합니다.
이런 식으로 suffix link를 정의했을 경우, 팰린드롬 $ S $의 모든 팰린드롬 suffix를 보는 과정은 $ S $에 해당하는 정점의 suffix link를 타고 $ I $를 만날 때까지 올라가면서 각 정점을 보는 과정으로 변환할 수 있습니다.
Construction
어떤 문자열 $ S $의 eertree를 만들기 위해서는 빈 문자열의 eertree에서 시작해서 $ S $의 각 문자를 앞에서부터 하나씩 eertree에 추가하면 됩니다. Motivation에서 증명한 바에 따르면 문자 하나를 추가할 때마다 eertree의 정점은 최대 하나씩 증가하고, 새로 추가된 정점 $ P $에 대해서 $ P $로 들어오는 edge 하나와 $ P $에서 나가는 suffix link가 하나씩 추가됩니다.
문자 $ c $를 $ S $에 추가하는 함수는 다음 단계를 거쳐 작동합니다:
- $ S $의 가장 긴 팰린드롬 suffix를 $ X $라고 합시다.
- $ cX $가 $ S $의 suffix인 경우 [$ X $가 $ I $인 경우] , 만약 $ cXc $ [ $ c $ ] 에 해당하는 정점이 이미 존재한다면 함수 실행을 종료합니다. 존재하지 않는다면, $ cXc $ [ $ c $ ]에 해당하는 정점 $ Y $를 만들고 $ X $에서 $ Y $로 가는 edge를 추가합니다.
- $ cX $가 $ S $의 suffix가 아닌 경우, $ X $를 $ suf(X) $ 로 바꾸고 $ cX $가 $ S $의 suffix가 될 때까지 이 과정을 반복합니다.
- $ X $를 $ suf(X) $로 바꿉니다.
- $ cX $가 $ S $의 suffix인 경우 [$ X $가 $ I $인 경우], $ Y $에서 $ cXc $ [ $ c $ ] 로 가는 suffix link를 만들고, 함수 실행을 종료합니다.
- $ cX $가 $ S $의 suffix가 아닌 경우, $ X $를 $ suf(X) $ 로 바꾸고 $ cX $가 $ S $의 suffix가 될 때까지 이 과정을 반복합니다.
요약하면 새로운 문자를 추가할 때마다 전체 문자열의 가장 긴 팰린드롬 suffix를 찾고, 두 번째로 긴 팰린드롬 suffix를 찾아 suffix link를 만들어주는데, 이를 위해서 기존 문자열의 팰린드롬 suffix를 긴 것부터 차례대로 보면서 조건에 맞는지 확인하는 단순한 과정입니다.
Analyzation
eertree에 문자를 하나 추가할 때마다 $ O(1) $ 만큼의 메모리를 사용하므로 eertree가 $ O(n) $의 공간복잡도를 차지한다는 것은 쉽게 알 수 있습니다. 그럼 시간 복잡도는 어떨까요?
문자를 추가하는 함수가 호출될 때마다 $ k_1 $번 suffix link를 타고 올라가면서 검사를 하고, 새로운 정점과 edge를 만든 다음에 다시 $ k_2 $번 suffix link를 타고 올라가면서 검사를 하고, 새로운 suffix link를 만듭니다. 따라서 eertree를 만드는 전체 비용은 각 함수에 대한 $ k_1 $과 $ k_2 $값의 합에 따라 결정이 되겠네요.
이를 분석하기 위해서 함수 호출 전후의 최장 팰린드롬 suffix의 첫 문자의 위치를 관찰해봅시다. edge를 만들기 위해 suffix link를 타고 올라가면서 비교한 횟수가 한 번 많아질 때마다 최장 팰린드롬 suffix의 첫 문자는 적어도 오른쪽으로 한 칸 이동하는데, suffix link를 타고 올라갈수록 팰린드롬의 길이가 적어도 한 칸 줄어들기 때문입니다. 마지막에 edge를 만들어 주면서 첫 문자가 왼쪽으로 한 칸 이동하므로 $ k_1 $번의 비교를 수행한 경우 첫 문자는 적어도 오른쪽으로 $ k_1 - 1 $칸 만큼 이동하게 됩니다.
그런데 문자열의 길이가 $ n $이므로 최장 팰린드롬 suffix의 첫 문자는 $ n $칸 초과 오른쪽으로 이동할 수 없습니다. 즉 $ \sum (k_1-1) \leq n$ 이라는 부등식을 얻습니다. $ n $번의 함수 호출에 대한 $ k_1 $의 합이 $ O(n) $ 이라는 결론을 얻었네요. $ k_2 $의 합이 $ O(n) $ 이라는 것도 비슷한 부등식을 세워서 얻을 수 있습니다. 따라서 suffix link를 타고 올라가는 과정의 시간 복잡도는 $ O(n) $이 됩니다.
마지막으로 새로운 정점을 삽입할 때 해당 정점이 이미 존재하는 지 체크하는 과정의 분석을 마치면 최종 시간 복잡도를 결정지을 수 있습니다. $ X $에서 $ Y $로 가는 edge를 추가해야 한다고 할 때, $ Y $가 이미 eertree 상에 존재했다면 $ X $에서 $ Y $로 가는 edge가 이미 존재했었어야 합니다. 이는 각 정점마다 균형 이진 트리를 관리하여 가능한 문자의 개수 $ \sigma $에 대해 $ O(log\sigma) $ 시간에 판별이 가능합니다. 또는, $ \sigma $의 값이 크지 않은 경우 길이 $ \sigma $인 배열을 정점마다 관리하여 $ O(1) $ 시간에 판별하는 방법도 가능합니다.
결론적으로, 최종 시간 복잡도는 $ O(nlog\sigma) $ 가 되며, 실제로 $\sigma$가 크지 않은 대부분의 상황 (대회 등) 에서는 공간 복잡도 $ O(n\sigma) $, 시간 복잡도 $ O(n) $이 요구되는 방법을 주로 사용합니다.