EERTREE (Palindromic Tree)

이 글은 다음 논문(EERTREE: An Efficient Data Structure for Processing Palindromes in Strings)을 바탕으로 작성된 글입니다. 이 글의 그림은 이 논문에서 가져왔습니다.

 

개요

Eertree는 문자열의 회문을 관리하는 자료구조입니다.

Eertree를 설명하기에 앞서, 몇가지 정의를 내리고 시작하겠습니다.

• 문자열은 \(w = w[1..n]\)과 같이 표현하고, 문자열의 i번째 문자는 S[i]와 같이 표현합니다.
• 문자의 종류의 수를 \(\sigma\)로 표현합니다.
• 어떤 \(i, j\)에 대해 \(u = w[i..j]\)라면 \(u\)는 \(w\)의 부분 문자열(substring)입니다.
• 어떤 \(i\)에 대해 \(u = w[1..i]\)라면 \(u\)는 \(w\)의 접두사(prefix)이고, \(u = w[i..n]\)라면 \(u\)는 \(w\)의 접미사(suffix)입니다.
• 어떤 문자열의 prefix인 palindrome을 prefix-palindrome, suffix인 palindrome을 suffix-palindrome이라 합니다.
• 문자열 \(S\)의 가장 긴 suffix-palindrome을 \(maxSuf(S)\)로 표현합니다.

Eertree의 구현

Eertree에서, 문자열 뒤에 문자 \(c\)를 추가하는 연산 \(Add(c)\)를 사용할 수 있습니다.

\(Add(c)\)에서 다음과 같은 명제가 성립합니다.

 

Lemma. 문자열 \(S\)에서 \(Add(c)\)를 호출했을 때, 문자열에 새로 나타나는 palindrome은 최대 한 개이며 이 palindrome은 \(Sc\)의 가장 긴 suffix-palindrome이다.

 

Proof. \(Sc\)의 가장 길지 않은 suffix-palindrome이 새로 나타났다고 가정해봅시다. 이 palindrome은 가장 긴 suffix-palindrome에 포함되어 있습니다. 가장 긴 suffix-palindrome의 prefix에도 이 palindrome이 존재하므로 모순입니다.

 

위 성질을 바탕으로 palindrome을 관리할 수 있는 루트가 있는 방향성 트리를 구성합니다.

• 트리의 각 정점 \(v\)는 각 정점이 나타내는 문자열의 길이 \(len[v]\)를 저장하고 있고, 초기 상태에서 짝수와 홀수 길이의 palindrome을 모두 저장하기 위해 길이가 \(-1, 0\)인 가상의 문자열을 나타내는 정점을 추가합니다.
• 트리의 각 간선은 문자가 적혀있으며 문자 \(c\)와 문자열 \(v\)에 대해 \(c\)가 적힌 간선은 두 정점 \(v\)와 \(cvc\)를 연결합니다.
• 각 정점 \(u\)에는 suffix link \(link[u]\)가 정의되며, \(u\)와 같지 않으면서 가장 긴 \(u\)의 suffix-palindrome을 향해 연결되어 있습니다.
• \(link[c] = 0, link[0] = link[-1] = -1\)로 정의됩니다.

 

문자열 eertree의 eertree. 검은색이 간선, 파란색이 suffix link입니다. 

문자열 \(S[1..n]\)의 eertree를 만들기 위해 \(add(S[1]), add(S[2]), \dots , add(S[n])\)를 순서대로 호출합니다.

현재 문자열 \(T = S[1..i]\)까지 구성하였고, \(add(a)\)를 호출하는 상황을 생각해봅시다.

새로 추가되는 palindrome을 찾기 위해 \(maxSuf(Ta)\)을 찾아야 합니다.

어떤 \(T\)의 suffix-palindrome \(Q\)에 대해 \(aQa\)가 \(Ta\)의 suffix인 가장 긴 \(Q\)를 찾으면, \(aQa\)가 \(Ta\)의 가장 긴 suffix-palindrome이 되므로 이러한 \(Q\)를 찾으면 됩니다.

\(maxSuf(T)\)부터 시작하여 이런 \(Q\)를 찾거나 \(-1\)에 도달할 때까지 suffix link를 타고 올라갑니다. (길이 \(k\)의 노드를 탐색중이라면 \(T[i - k] = a\)를 만족하는지 체크해주면 됩니다.)

찾은 \(Q\)에서 \(Q\)와 \(aQa\)를 잇는 간선이 없다면 새로운 palindrome을 찾았으므로 길이가 \(|Q| + 2\)인 새 정점 \(P\)를 추가하여 \(Q\)에 연결해줍니다.

새로 정점을 추가했을 경우 suffix link를 찾아야 하는데, \(P\)의 suffix link는 \(Ta\)의 두번째로 긴 suffix-palindrome으로 연결되어 있으므로 \(Q\)의 suffix link부터 위 탐색을 계속 진행하여 찾을 수 있습니다.

이제 시간복잡도를 분석해 봅시다. \(add(a)\)를 호출했을 때 \(Q\)와 \(aQa\)를 잇는 간선의 존재성을 찾는 것은 std::map 등의 자료구조를 통해 \(O(log \sigma )\)에 가능합니다. \(maxSuf\)의 첫번째 문자에 해당하는 문자의 위치는 suffix link를 탈때 오른쪽으로 이동하고, 새 문자를 추가했을 때 \(1\)만큼 왼쪽으로 이동합니다. 따라서 suffix link를 타는 횟수는 총 \(O(n)\)번이므로 총 시간복잡도는 \(O(nlog \sigma )\)가 됩니다.

 

Eertree를 사용한 문제풀이

eertree를 사용하면 다음 두 문제를 간단하게 해결할 수 있습니다.

APIO 2014. 팰린드롬

문자열 \(S\)에서 정점 \(v\)가 \(S\)에 등장하는 횟수를 \(occ[v]\), 어떤 \(i\)에 대해 \(maxSuf(S[1..i])\) = \(v\)를 만족하는 \(i\)의 개수를 \(occAsMax[v]\)라고 합시다.

이 때, 다음과 같은 관계식이 성립합니다:

\(occ[v] = occAsMax[v] + \sum_{u:link[u]=v} occ[u]\)

\(occAsMax\)는 eertree를 만드는 과정에서 쉽게 구할 수 있으므로 eertree를 모두 구성한 뒤 bottom-up 방식으로 \(occ[v]\)를 모두 구할 수 있습니다.

모든 정점 \(v\)에 대해\(occ[v] * len[v]\)의 최댓값이 답이 됩니다.

MIPT Fall Programming Training Camp 2014. Palindromic Pairs

문자열 \(S\)가 주어졌을 때, \(S[i..j]\)와 \(S[j+1..k]\)가 모두 팰린드롬인 \( (i, j, k) (1 \le i \le j \lt k \le |S|)\)의 개수를 구하라.

 

\(maxSuf[j] = maxSuf(S[1..j])\), 정점 \(v\)에 대해 \(sufCount[v]\)를 \(v\)의 suffix-palindrome의 개수라고 합시다.

\(sufCount[v] = sufCount[link[v]] + 1\)이므로 트리를 내려오면서 \(sufCount\)의 값을 채울 수 있습니다.

어떤 \(j\)에 대해 \(S[i..j]\)가 팰린드롬인 \(i\)의 개수는 \(S[1..j]\)의 suffix-palindrome의 개수와 같으므로 \(sufCount[maxSuf[j]]\)가 됩니다.

비슷한 방식으로 \(maxPref\)와 \(prefCount\)를 정의하면, 이 두 배열은 \(S\)를 뒤집은 문자열의 eertree에서 채울 수 있습니다.

답은 다음 식의 값이 됩니다.

\(\sum_{j=1}^{n-1} sufCount[maxSuf[j]] * prefCount[maxPref[j + 1]] \)

Eertree의 확장 - 문자열 여러개의 Eertree

여려개의 문자열을 비교해야하는 문제를 해결할 때, 한번에 eertree를 만들면 간단하게 해결 가능할 수 있습니다.

joint eertree \(eertree(S_1, S_2, \dots , S_k)\)는 다음과 같이 만들어집니다.

처음으로 \(S_1\)의 eertree를 만들고, \(S_2\)와 \(S_1\)를 끊어주기 위해 \(maxSuf\)의 값을 \(0\)으로 초기화하고 \(S_2\)의 eertree를 만듭니다. 똑같은 방식으로 \(S_k\)까지 모두 eertree를 만들 수 있습니다.

eertree의 각 정점에는 길이 \(k\)의 boolean 배열 flag가 저장되어 있습니다. 이 배열의 \(i\)번째 값은 그 정점의 문자열이 \(S_i\)에 포함되어 있는지를 나타내는 값입니다. \(Add\)를 호출할 때 마다 현재 \(maxSuf\)의 flag를 \(1\)로 업데이트 해주면 flag 배열의 값을 모두 구할 수 있습니다.

joint eertree로 다음과 같은 문제를 해결할 수 있습니다.

문제	풀이
문자열 \(k\)개가 주어졌을 때, 모든 문자열의 substring인 palindrome의 개수를 구하여라.	\(eertree(S_1, S_2, \dots , S_k)\)에서 flag의 값이 모두 \(1\)인 정점의 개수를 구하면 됩니다.
문자열 \(k\)개가 주어졌을 때, 모든 문자열의 substring인 palindrome 중 가장 긴 것을 구하여라.	\(eertree(S_1, S_2, \dots , S_k)\)에서 flag의 값이 모두 \(1\)인 가장 긴 길이의 정점을 구하면 됩니다.
두 문자열 \(S, T\)에 대해 \(T\)보다 \(S\)에서 더 많이 나타나는 palindrome의 개수를 구하여라.	\(eertree(S, T)\)를 만들고 \(occ_S\)와 \(occ_T\)를 계산합니다. (\(occ\)에 대해서는 위 문제 팰린드롬에 설명되어 있습니다.) \(occ_S[v] > occ_T[v]\)인 정점 v의 개수가 답이 됩니다.
두 문자열 \(S, T\)에 대해 \(S[i..i+k] = T[j..j+k]\)인 \((i, j, k)\)의 개수를 구하여라.	\(eertree(S, T)\)를 만들고 \(occ_S\)와 \(occ_T\)를 계산합니다. \(sum_{v } \; occ_S[v] * occ_T[v]\) 의 값이 답이 됩니다.

 (2번째 문제는 UCPC 2018 예선의 가장 긴 공통부분 팰린드롬과 동일한 문제입니다.)

 

Eertree의 확장 - quickLink

\(add\) 연산 뿐만 아니라 문자열의 마지막 문자를 제거하는 \(pop\) 연산이 필요한 경우를 생각해봅시다.

이 경우 suffix link를 타는 횟수가 \(O(n^2)\)번이기 때문에 시간복잡도 \(O(nlog \sigma )\)가 보장되지 않게 됩니다.

이런 경우에서의 최적화를 위해, 새로운 link인 quickLink를 정의합니다.

정점 \(v\)에 대해 \(v\)에서 \(link[v]\)의 앞에 오는 문자를 \(b = v[|v|-|link[v]|]\)라 하면 \(quickLink[v]\)는 앞에 오는 문자가 \(b\)가 아닌 \(link[v]\)의 가장 긴 suffix-palindrome으로 정의됩니다.

정점 \(v\)가 만들어질 때, \(quickLink[v]\)는 다음과 같이 구할 수 있습니다.

if (S[n - len[link[v]] == S[n - len[link[link[v]]])
    quickLink[v] = quickLink[link[v]]
else
    quickLink[v] = link[link[v]]

문자열 \(T\)에 \(Add(a)\)를 호출할 때, quickLink를 사용할 때도 동일하게 \(aQa\)가 \(Ta\)의 suffix인 \(T\)의 가장 긴 suffix-palindrome \(Q\)를 찾아야 합니다. \(Q = maxSuf(T)\)일 때와 \(Q = link[maxSuf(T)]\)일 때를 검사해 보고, 그 뒤로는 quickLink를 사용하여 건너뛰면서 탐색합니다.

 

eertree에서 quickLink로 이루어진 경로의 길이는 \(O(logn)\)이 되어 \(Add\)를 호출했을 때의 탐색을 \(O(logn)\) 시간에 수행할 수 있습니다.

 

(증명의 원 논문, Lemma 1~5)

문자열 \(x, y\)에 대하여 \(y\)가 \(x\)의 prefix이면서 suffix이면 \(y\)는 \(x\)의 border이고, 여기서 \(x \neq y\)일 경우 proper border 라고 정의합니다.

 

Lemma 1. \(y\)가 palindrome \(x\)의 suffix일 때, \(y\)가 palindrome인 것은 \(y\)가 border인 것의 필요충분조건이다.

 

Proof. \(x[1..|y|]\)는 \(y = x[|x|-|y|+1..|x|]\)를 뒤집은 문자열이기 때문에, 두 문자열이 같다는 것은 \(y\)가 palindrome이라는 것과 동치입니다.

 

Lemma 2. \(y\)가 \(x\)의 \(|x| \le 2|y|\)를 만족하는 border일 때, \(y\)가 palindrome인 것은 \(x\)가 palindrome인 것의 필요충분조건이다.

 

Proof. Lemma 1에 의해 \(x\)가 palindrome이라면 \(y\)도 palindrome입니다. \(y\)가 palindrome이라면 \(i(i \le n/2)\)에 대하여, \(x[i] = y[i] = y[|y| - i + 1] = x[|x| - i + 1]\)입니다. 팰린드롬의 정의에 따라 \(x\)는 palindrome입니다.

 

어떤 양의 정수 \(p \le |x|\)에 대해 \(x\)가 \(w^{ \infty }\) (\(w\)를 무한히 이어붙인 문자열)의 부분문자열인 길이 \(p\)의 문자열 \(w\)가 존재하면 \(p\)가 \(x\)의 주기(period)라고 정의합니다.

문자열 \(y\)가 \(x\)의 proper border이기 위해서는 \(|x| - |y|\)가 \(x\)의 주기여야 한다는 것이 알려져 있습니다.

따라서 Lemma 1을 통해 다음과 같은 Lemma를 얻을 수 있습니다.

 

Lemma 3. \(y\)가 palindrome \(x\)의 proper suffix(\(x\)와 같지 않은 suffix)일 때, \(y\)가 palindrome인 것은 \(|x| - |y|\)가 \(x\)의 주기인 것의 필요충분조건이다. 특히, \(y\)가 가장 긴 palindrome인 것은 \(|x| - |y|\)가 \(x\)의 가장 작은 주기인 것의 필요충분조건이다.

 

이제 다음과 같은 중요한 성질을 얻을 수 있습니다.

 

Lemma 4. palindrome \(x\)의 가장 긴 palindromic proper suffix을 \(y\), \(y\)의 가장 긴 palindromic proper suffix을 \(z\)라고 하자. (\(y = maxSuf(x), z = maxSuf(y)\)) 여기서 \(u\), \(v\)를 \(x = uy\), \(y = vz\)를 만족하는 문자열이라 하자. 이 때

(1) \(|u| \ge |v|\) 이고

(2) \(|u| \gt |v|\) 이면 \(|u| \gt |z|\) 이다.

 

Proof. 

(1) Lemma 3에 의하여 \(|u| = |x| - |y|\)는 \(x\)의 가장 작은 주기이고, \(|v| = |y| - |z|\)는 \(y\)의 가장 작은 주기입니다. \(y\)가 \(x\)의 부분문자열이므로 \(|u|\)는 \(y\)의 주기이고, 이는 \(|v|\)보다 작아질 수 없습니다.

(2) \(y = vz\)가 팰린드롬이므로 \(y\)는 \(x\)의 border입니다. \(w\)를 \(vw = x\)를 만족하는 문자열이라 합시다.

\(|u| \gt |v|\)일 때 \(|u| \le |z|\)라고 가정하면 \(z\)는 \(w\)의 border이고 \(|w| = |zu| \le 2|z|\)이므로 Lemma 2에 따라 \(w\)는 palindrome입니다. \(|y| \lt |w|\)이므로 \(y\)가 \(x\)의 가장 긴 palindromic proper suffix라는 정의에 모순입니다.

 

문자열 \(S\)에 대해 \(gap(S)\)을 \(|S| - |maxSuf(S)|\)라 하고, 수열 \(P\)를 \(P = \{ gap(S), gap(maxSuf(S)), gap(maxSuf(maxSuf(S))), \dots \} \) 라고 합시다. 

 

Lemma 5. 수열 \(P\)는 단조감소하고 최대 \(O(log|S|)\)개의 서로 다른 수가 있다.

 

Proof.  Lemma 4의 (1)에 의해 \(P\)는 단조감소합니다.

만약 gap의 값이 바뀐다면 Lemma 4의 (2)에서 \(|x| \gt |u| + |z| \gt 2|z|\)이므로 문자열의 길이가 두 배 이상 감소합니다. 그러므로 \(P\)에는 최대 \(O(log|S|)\)개의 서로 다른 수가 있습니다.

 

이제 quickLink로 이루어진 경로의 길이를 계산해봅시다.

만약 quickLink를 타도 gap의 값이 똑같다면 앞에 오는 문자도 똑같게 됩니다.

그러므로 quickLink로 이루어진 경로의 길이는 \(O(logn)\)입니다.

 

Eertree의 확장 - directLink

각 노드에 대해 \( \sigma \)개의 direct link를 만듭니다. 정점 \(v\)에서 \(directLink[v][c]\)는 \(c\)가 앞에 오는 \(v\)의 가장 긴 suffix-palindrome으로 정의합니다.

문자열 \(T\)에서 \(c\)가 앞에 오는 가장 긴 suffix-palindrome \(Q\)를 찾을 때 \(Q = maxSuf(T)\) 또는 \(Q = dirctLink[maxSuf(T)][c]\)가 되므로 directLink를 통해 상수 시간에 suffix의 탐색을 수행할 수 있습니다.

\(directLink[v]\)와 \(directLink[link[v]]\)는 \(v\)에서 \(link[v]\) 앞에 오는 문자 \(c\)를 제외하면 모두 같은 값을 가집니다. 그러므로 \(directLink\) 배열을 만들 때, \(link[v]\)를 찾은 다음 \(directLink[v]\)에 \(directLink[link[v]]\)를 그대로 복사한 뒤 \(directLink[v][c] = link[v]\)로 변경시켜주면 됩니다.

\(directLink\) 배열을 그냥 복사하면 많은 메모리와 시간을 소모하게 됩니다. 최적화를 위해, persistent tree (fully persistent balanced binary search tree)를 사용할 수 있습니다. 문자를 key로 하는 하나의 persistent tree를 통해 각 노드의 \(directLink\) 배열을 저장합니다. 한 노드의 \(directLink\) 배열에서 업데이트된 위치의 수는 정의에 따라 최대 \(\sigma \)개이고, 위 quickLink에서의 증명을 통해 \(O(logn)\)개입니다. persistent tree의 크기가 \(O(min(\sigma , logn))\)이므로 전체 \(O(min(log\sigma , loglogn))\)의 메모리와 시간에 \(directLink\)를 구현할 수 있습니다.

 

방법	\(n\)번의 호출의 시간복잡도	\(1\)번의 호출의 시간복잡도	한 정점의 공간복잡도
일반 quickLink directLink	\(O(nlog\sigma )\) \(O(nlog\sigma )\) \(O(nlog\sigma )\)	\(O(n)\) \(O(logn)\) \(O(log\sigma )\)	\(O(1)\) \(O(1)\) \(O(min(log\sigma , loglogn))\)

 

 

팰린드롬으로 분할하기 (Factorizations into Palindromes)

문자열을 \(k\)개의 팰린드롬으로 분할하는 문제를 \(k\)-factorization 문제, 문자열을 \(k\)개의 팰린드롬으로 분할할 수 있는 최소 \(k\)를 그 문자열의 Palindromic length라 합시다. 이 챕터에서는 \(k\)-factorization 문제를 eertree를 통해 빠르게 푸는 것을 목적으로 합니다.

 

Lemma 1. 길이가 \(n\)인 문자열 \(S\)의 \(k\)-factorization이 주어졌을 때, 양의 정수 \(t (k+2t \le n)\)에 대해 \(S\)의 \((k+2t)\)-factorization을 \(O(n)\) 시간에 구할 수 있다.

 

Proof. 나눠진 각 팰린드롬을 \(P_1, \dots , P_k\) \((S = P_1 \dots P_k, k \le n - 2)\)라고 합시다. \(S\)를 \(k + 2\)개의 팰린드롬으로 나눌 수 있다는 것만 보여도 충분합니다. 어떤 \(i\)에 대해 \(|P_i| \ge 3\)이라면 \(P_i\)를 첫 글자, 마지막 글자, 남은 문자열로 \(3\)개의 팰린드롬으로 나눌 수 있습니다. 그렇지 않다면, 길이 \(2\)인 팰린드롬이 두 개 이상 있으므로 이 \(2\)개의 문자열을 각각 두 개의 문자로 나눠줄 수 있습니다.

 

이제 \(k\)-factorization 문제를 2개의 비슷한 문제로 줄일 수 있습니다. 문자열을 가장 작은 홀수(와 짝수)개의 팰린드롬으로 나누는 문제를 해결하면 \(k\)-factorization 문제를 해결할 수 있습니다.

이 문제를 해결하기 위해, 먼저 palindromic length를 구하는 알고리즘을 설계합니다.

 

길이 \(n\)의 문자열 \(S\)에서 \(ans[i]\)를 \(S[1..i]\)의 palindromic length로 정의합니다.

그러면 \(ans[i] = 1 + min\{ ans[j] \; | \; S[j+1..i] \; is \; a \; palindrome \} \)가 만족하게 됩니다.

\(ans\)를 효율적으로 계산하기 위해 eertree에서 두 파라미터 \(diff[v] = len[v] - len[link[v]]\)과 series link \(seriesLink[v]\)를 새로 정의합니다. series link는 \(diff\)의 값이 \(diff[v]\)와 다른 가장 긴 suffix-palindrome으로 정의됩니다. 두 배열은 다음과 같이 구할 수 있습니다.

if (diff[v] == diff[link[v]])
    seriesLink[v] = seriesLink[link[v]]
else
    seriesLink[v] = link[v]

그리고 \(ans[n]\)은 다음과 같이 \(O(n)\)에 구할 수 있습니다.

ans[n] = \(\infty \)
for (v = maxSuf(S[1..n]); len[v] > 0;  v = link[v])
    ans[n] = min(ans[n], ans[n - len[v]] + 1)

이 코드는 series link를 사용해 이렇게 바꿔 적을 수 있습니다.

int getMin(u)
    res = \(\infty \)
    for (v = u; len[v] > len[seriesLink[u]]; v = link[v])
        res = min(res, ans[n - len[v]] + 1)
    return res
ans[n] = \(\infty \)
for (v = maxSuf; len[v] > 0; v = seriesLink[v])
    ans[n] = min(ans[n], getMin(v))

이 코드에서, \(getMin\) 함수의 속도를 개선해 봅시다.

팰린드롬 \(u\)에서 \(u\)부터 \(seriesLink[u]\)까지의 경로에 있는 정점들을 \(u\)의 \(series\)라고 합시다. (\(seriesLink[u]\)는 포함하지 않음) \(getMin(u)\)는 \(u\)의 \(series\)를 탐색합니다. \(u\)의 \(series\)가 하나의 정점만을 포함하는 경우 \(getMin(u)\)는 \(O(1)\) 시간에 계산할 수 있으므로, 2개 이상의 정점을 포함하는 경우만 생각하겠습니다.

문자열 \(S\)의 suffix-palindrome \(u\)가 \(u = maxSuf(S)\)이거나 어떤 \(S\)의 suffix-palindrome \(v\)에 대해 \(u = seriesLink[v]\)일 경우 \(u\)가 \(leading\)이라고 합시다. 이제 몇 개의 lemma가 필요합니다.

 

Lemma 2. 길이가 \(l (l \ge n/2)\)인 팰린드롬 \(v\)가 문자열 \(S[1..n]\)의 prefix이면서 suffix이면, \(S\)는 팰린드롬이다.

 

Proof. \(i(i \le n/2)\)에 대하여, \(S[i] = v[i] = v[l - i + 1] = S[n - i + 1]\)입니다. 팰린드롬의 정의에 따라 \(S\)는 팰린드롬입니다.

 

Lemma 3. \(v\)가 문자열 \(S[1..n]\)의 leading suffix-palindrome이고 \(u = link[v]\)가 \(v\)의 series에 속할 때, \(u\)는 \(v\) 안에서 suffix와 prefix로써 정확히 두 번 나타난다.

 

Proof. \(i = n - |v| + 1\)이라 합시다. 그러면 \(v = S[i..n]\)이고, \(u = S[i+diff[v]..n] = S[i..n-diff[v]]\)입니다. \(diff[u]=diff[v]\)이기 때문에, \(diff[v] \le |v|/2\)이고 \(|u| \ge |v|/2\)입니다. 만약 \(i \lt k \lt i+diff[v]\)와 \(S[k..t] = u\)를 만족하는 \(k, t\)가 존재한다면 Lemma 2에 따라 \(S[k..n]\)은 팰린드롬입니다. 이 팰린드롬은 \(link[v]\)보다 긴 \(v\)의 suffix이므로 모순됩니다.

 

Lemma 4. \(v\)가 문자열 \(S[1..n]\)의 leading suffix-palindrome이고 \(u = link[v]\)가 \(v\)의 series에 속할 때, \(u\)는 \(S[1..n-diff[v]]\)의 leading suffix-palindrome이다.

 

Proof. \(u\)가 leading이 아니라면, \(link[z] = u\)이고 \(diff[z] = diff[u]\)인 \(S[1..n-diff[v]]\)의 suffix-palindrome \(z = S[j..n-diff[v]]\)가 존재해야 합니다. \(u\)가 \(v\)와 \(z\)의 prefix이면서 suffix이고 \(|z| = |v| \le 2|u|\)이므로 \(z = v\)입니다. 그러면 \(w = S[j..n]\)은 Lemma 2에 의하여 팰린드롬입니다. 만약 \(v\)보다 길고 \(w\)가 아닌 \(w\)의 suffix-palindrome \(v\prime \)이 존재한다면 \(v\prime \)은 \(u\)로 시작하는데, 이 \(u\)는 \(z = S[j..n-diff[v]]\)의 prefix도 suffix도 아니므로 Lemma 3에 모순됩니다. 그러므로 \(link[w] = v\)이고 \(diff[w] = diff[v]\)가 되는데, 이는 \(v\)가 leading이라는 가정에 모순됩니다.

 

Lemma 5. eertree에서, series link로 이루어진 경로의 길이는 \(O(logn)\)이다.

 

Proof. quick link의 경로의 길이에 대한 증명과 거의 동일합니다.

 

Lemma 5에 의해, 위 코드에서 \(ans[n]\)을 구할 때 \(getMin\)을 \(O(logn)\)번 호출하게 됩니다. 이제 \(getMin\) 함수를 \(O(1)\)에 수행하는 방법을 생각해 봅시다.

 

\(S[1..n]\)에서 \(v\)의 series와 \(S[1..n-diff[v]]\)에서 \(link[v]\)의 series. 다음 series의 Leading palindrome은 점선으로 나타내었다. \(getMin\)함수는 파란색으로 표시된 위치들에서 \(ans\)의 최솟값을 반환한다.

이 그림에서 \(v\)와 \(link[v]\)의 series가 \(v\)의 series의 마지막 팰린드롬을 제외하면 모두 매칭된다는 것을 알 수 있습니다. 그러므로 \(getMin(v)\)를 계산할 때 마지막 위치 이외에는 \(ans[n-diff[v]]\)를 구하는 과정에서 이미 계산되어 있습니다. 만약 이런 최솟값을 잘 기억해둘 수 있다면 \(getMin\) 함수를 상수 시간에 계산할 수 있을 것입니다.

이러한 최솟값의 저장을 위해 eertree의 정점에서 새 파라미터 \(dp\)를 정의합니다. \(dp[v]\)의 값은 \(getMin(v)\)가 호출될 때마다 (즉, \(v\)가 leading suffix-palindrome이 될 때마다) 갱신됩니다. \(getMin(v)\)를 계산할 때 Lemma 3, 4에 의해 \(dp[link[v]]\)를 참조하여 계산할 수 있습니다. (Lemma 4에 의해 \(link[v]\)는 leading이고 Lemma 3에 의해 \(link[v]\)는 \(v\)의 prefix와 suffix로만 등장하므로) 이제 다음과 같이 \(getMin\) 함수를 적을 수 있습니다.

int getMin(v)
    dp[v] = ans[n - (len[seriesLink[v]] + diff[v])] // 마지막 값
    if (diff[v] == diff[link[v]]) // series의 크기가 2 이상
        dp[v] = min(dp[v], dp[link[v]])
    return dp[v] + 1

이 코드에서 \(dp[v]\)는 \(v\)의 series의 마지막 원소의 앞에 오는 위치의 \(ans\)값으로 초기화됩니다. 만약 series에 다른 원소가 없다면 다른 계산은 필요없습니다. 만약 있다면, \(dp[link[v]]\)를 통해 series의 다른 원소들에 대해서도 계산해줄 수 있습니다.

이 방법을 통해 palindromic length를 \(O(nlogn)\)에 계산할 수 있습니다. 이제 \(k\)-factorization 문제로 돌아옵시다.

\(k\)-factorization 문제를 풀기 위해서 최소 팰린드롬 분할을 짝수와 홀수를 나눠서 계산해야 합니다. 이는 위 palindromic length를 구하는 방법을 약간만 변형하여 구할 수 있습니다. 홀짝을 고려하기 위해 \(ans\)와 \(dp\)를 각각 두개의 파라미터 \(ans_o, ans_e\)와 \(dp_o, dp_e\)로 분할합니다. 그리고 \(ans_o\)는 \(dp_e\), \(ans_e\)는 \(dp_o\), \(dp_o\)는 \(ans_o\), \(dp_e\)는 \(ans_e\)를 참조합니다.

int getMin(v, p)
    dp[v][p] = ans[n - (len[seriesLink[v]] + diff[v])][p]
    if (diff[v] == diff[link[v]]) 
        dp[v][p] = min(dp[v][p], dp[link[v]][p])
    return dp[v][p] + 1
ans[n][0] = ans[n][1] = \(\infty \)
for (v = maxSuf; len[v] > 0; v = seriesLink[v])
    ans[n][0] = min(ans[n][0], getMin(v, 1))
    ans[n][1] = min(ans[n][1], getMin(v, 0))

이제 Lemma 1에 의해 \(k\)-factorization을 \(O(nlogn)\)에 해결할 수 있습니다.

 

\(k\)-factorization의 전체 소스 코드입니다. 역추적을 위해 \(dp\)를 최소가 되는 위치와의 거리로 정의했습니다. (따로 \(k\)-factorization의 문제를 찾지 못해서 채점 해보지는 못했습니다. 실수가 있을 수도 있습니다.)

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
using namespace std;
 
struct node
{
    int len, diff, dp[2];
    node *sfl, *srl;
    map<char, node*> nt;
    node() : len(0), diff(0), dp(), sfl(nullptr), srl(nullptr), nt(map<char, node*>()) {
        dp[0] = dp[1] = 0;
    };
};
 
const int inf = 1000000000;
int ans[1000009][2], rp[1000009][2];
vector<node*> ert, mxsuf;
string ers;
 
void init()
{
    ert.push_back(new node());
    ert[0]->len = -1; ert[0]->sfl = ert[0]; ert[0]->srl = ert[0];
    ert.push_back(new node());
    ert[1]->len = 0; ert[1]->sfl = ert[0]; ert[1]->srl = ert[0];
    ers += ".";
    mxsuf.push_back(ert[1]);
    ans[0][0] = 0; ans[0][1] = inf;
}
 
void add(char c)
{
    int pi = (int)ers.length() - 1;
    ers += c;
    node *q = mxsuf[pi];
    while (q->len != -1 && ers[pi - q->len] != c)
        q = q->sfl;
    if (q->nt.find(c) != q->nt.end()) {
        mxsuf.push_back(q->nt[c]);
        return;
    }
    node* nn = new node();
    q->nt[c] = nn;
    nn->len = q->len + 2;
    q = q->sfl;
    while (q->len != -1 && ers[pi - q->len] != c)
        q = q->sfl;
    if (nn->len == 1) nn->sfl = ert[1];
    else nn->sfl = q->nt[c];
    nn->diff = nn->len - nn->sfl->len;
    if (nn->diff != nn->sfl->diff) nn->srl = nn->sfl;
    else nn->srl = nn->sfl->srl;
    ert.push_back(nn);
    mxsuf.push_back(nn);
}
 
int dp(int n, node *v, int t)
{
    v->dp[t] = v->srl->len + v->diff;
    if (v->diff == v->sfl->diff) {
        if (ans[n - v->dp[t]][t] > ans[n - (v->sfl->dp[t] + v->diff)][t])
            v->dp[t] = v->sfl->dp[t] + v->diff;
    }
    return v->dp[t];
}
 
void ps(int n)
{
    for (int i = 0; i < 2; i++) {
        ans[n][i] = inf; rp[n][i] = -1;
        for (node *v = mxsuf[n]; v->len > 0; v = v->srl) {
            int r = dp(n, v, 1 - i);
            if (ans[n][i] > ans[n - r][1 - i] + 1) {
                ans[n][i] = ans[n - r][1 - i] + 1;
                rp[n][i] = r;
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    string s; cin >> s;
    int n, k;
    n = s.length(); cin >> k;
    init();
    for (int i = 0; i < n; i++) {
        add(s[i]);
        ps(i + 1);
    }
    int t = (k % 2);
    if (k < ans[n][t]) {
        cout << -1 << '\n';
        return 0;
    }
    vector<int> v, ansv;
    int pr = n, pk = t;
    while (pr > 0) {
        v.push_back(rp[pr][pk]);
        pr -= rp[pr][pk]; pk = 1 - pk;
    }
    reverse(v.begin(), v.end());
    k -= v.size();
    for (int i = 0; i < v.size(); i++) {
        if (v[i] >= 3 && k > 0) {
            int c = min(k / 2, (v[i] - 1) / 2);
            for (int j = 0; j < c; j++) ansv.push_back(1);
            ansv.push_back(v[i] - 2 * c);
            for (int j = 0; j < c; j++) ansv.push_back(1);
            k -= 2 * c;
        }
        else ansv.push_back(v[i]);
    }
    if (k > 0) {
        v.clear();
        for (int i = 0; i < ansv.size(); i++)
            v.push_back(ansv[i]);
        ansv.clear();
        for (int i = 0; i < v.size(); i++) {
            if (v[i] == 2 && k > 0) {
                ansv.push_back(1); ansv.push_back(1);
                k--;
            }
            else
                ansv.push_back(v[i]);
        }
    }
    int pi = 0;
    for (int i = 0; i < ansv.size(); i++) {
        cout << s.substr(pi, ansv[i]) << " ";
        pi += ansv[i];
    }
    cout << '\n';
    return 0;
}

 

관련 문제: 

BOJ 1509번. 팰린드롬 분할 (\(O(nlogn)\)에 해결할 수 있다.)

Codeforces #463 G. Palindrome Partition