접미사 배열의 조합적 성질

이 글은 GPT-4.5가 최종 편집하였다. 썸네일의 suffix array도 GPT가 그렸지만, 아쉽게도 틀렸다.

길이가 $n$인 문자열 $S$의 접미사 배열(Suffix Array, SA)이란, $S$의 모든 접미사(suffix) $S[i\dots]$들을 사전 순으로 정렬했을 때의 시작 인덱스 순열을 말한다. 예를 들어, $S = aba$라면 접미사들을 사전 순으로 정렬했을 때 $a < aba < ba$이므로, 접미사 배열은 0-based로 $[0, 2, 1]$이 된다. SA는 문자열 알고리즘에서 매우 중요한 자료구조로, 기본 개념에 대해서는 koosaga님의 글을 참고하면 좋다.

Inverse Problem

어떤 순열 $\sigma$가 주어졌을 때, 이를 접미사 배열로 하는 문자열은 몇 개나 존재할까? SA는 $S[\sigma(0)] \le \dots \le S[\sigma(n-1)]$라는 관계를 나타내므로, 우리는 이 등호가 언제 성립하지 않는지만 판별하면 된다.

만약 $S[\sigma(i)] = S[\sigma(i+1)]$이라면, $S[\sigma(i)+1\dots] < S[\sigma(i+1)+1\dots]$여야 한다. 이 정보는 순열 $\sigma$ 자체에 이미 포함되어 있다. 즉, $\sigma^{-1}(\sigma(i)+1) < \sigma^{-1}(\sigma(i+1)+1)$을 확인하면 된다. (단, $\sigma^{-1}(n) = -1$로 정의한다.) 전체 문자 종류가 $m$개이고, 이러한 $i$의 개수가 $r$개라면 가능한 문자열 $S$의 개수는 다음과 같다: $\binom{m+r}{n}$

연습 문제

• BOJ 13012. 접미사 배열 1
• BOJ 13013. 접미사 배열 2
• BOJ 13924. 접미사 배열 3

Counting Problem

반대로, 문자의 종류가 최대 $m \le n$개인 길이 $n$의 문자열이 가질 수 있는 접미사 배열의 총 가짓수 $SA(m, n)$는 얼마일까? 우선 다음 사실을 관찰할 수 있다:
$$\sigma^{-1}(\sigma(i)+1)>\sigma^{-1}(\sigma(i+1)+1) \implies S[\sigma(i)] < S[\sigma(i+1)]$$
이 조건을 만족하는 $i$는 최대 $m-1$개 존재할 수 있다. 여기서 $\tau(i) := \sigma^{-1}(\sigma(i)+1)$는 사실상 ${0, \dots, n-1}$에서 ${-1, \dots, n-1}$로 가는 injective 함수이며, image에서는 정확히 $\sigma(0)$만 빠져있다.

예컨대, $\sigma = \begin{pmatrix}0 & 1 & 2 \\ 1 & 0 & 2\end{pmatrix}$이라면 $\tau = \begin{pmatrix}0 & 1 & 2 \\ 2 & 0 & -1\end{pmatrix}$가 된다. 여기서 $\sigma(0)$보다 작은 값들에 1을 더하여 새로운 순열 $\tau'$를 만들 수 있으며, 이렇게 정의한 변환 $f : S_n \to S_n$, $f(\sigma) = \tau'$는 bijection이다. 편의상 $f(\sigma)$를 $\tilde{\sigma}$로 쓰자.

따라서 원래 문제는 $\tilde{\sigma}(i) > \tilde{\sigma}(i+1)$인 i의 개수(descent)가 최대 $m-1$개인 순열의 개수를 세는 문제로 환원된다. 역으로, descent가 $m-1$개 이하라면 descent를 기준으로 구간을 나누고 각 구간에 문자를 배정하는 방식으로 SA를 구성할 수 있다. 순열에서 정확히 $k$개의 descent를 가지는 순열의 수를 나타내는 Eulerian Number $A(n, k)$를 사용하면, 우리가 원하는 해답은 다음과 같이 표현할 수 있다: $$SA(m, n) = \sum_{i=0}^{m-1} A(n, i)$$
Eulerian Number는 생성함수를 이용해 $O(n \log n)$ 시간 내로 계산할 수 있다.

연습 문제

• BOJ 11393. 접미사 배열의 개수

Worpitzky's Identity

위 두 가지 관찰을 결합하면 유명한 Worpitzky의 항등식을 증명할 수 있다: $$x^{n} = \sum_{k=0}^{n-1} A(n, k) \binom{x+k}{n}$$
이는 Eulerian Number가 다항식 기저 변환과 유사한 구조를 가짐을 보여준다(예전 글 참고). 여기서 $\binom{x+k}{n}$가 반드시 다항식의 기저를 이루는 것은 아니지만 꽤 재미 있는 해석이다.

증명 아이디어는 간단하다. descent가 $r$개인 순열의 개수가 $A(n, r)$이며, 각 순열에 대해 가능한 문자열 개수가 $\binom{m+r}{n}$이므로, 모든 양의 정수 $m$에 대해 $$m^{n} = \sum_{k=0}^{n-1} A(n,r ) \binom{m+r}{n}$$
가 성립하고, 이는 다항식의 항등식을 의미한다.

With LCP Array (TBD)

접미사 배열만으로는 문자열을 유일하게 복원할 수 없지만, LCP(Longest Common Prefix) 배열까지 주어지면 복원이 가능해진다. LCP 배열에서 값이 0인 위치가 문자가 바뀌는 지점이 된다. 이 논문에 따르면, SA 없이 LCP 배열만 주어진 경우 특정 조건 하에 polynomial time으로 문자열 복원이 가능하지만, LCP 배열의 유효성(validity) 검증 문제는 NP-complete이다.