접미사 트리 (파트 2: Ukkonen의 알고리즘)

이전 글에서 이어집니다.

Ukkonen의 $O(m^3)$ 알고리즘

Ukkonen의 알고리즘은 접미사 트리를 $O(m)$에 만드는 알고리즘입니다. 하지만 이를 모두 설명하기에는 너무 복잡하니, 비효율적인 버전을 먼저 서술하고 시간 복잡도를 점차 줄여 나갑시다. (구현할 때도 파트 1을 먼저 구현하고, stress test 등으로 구현이 정확함을 확인하시는 것을 권합니다.)

$S[1..i]$의 접미사 트리를 $I_i$라고 표기합시다. Ukkonen의 알고리즘의 큰 그림은 $I_1$에서 시작해서 이것을 $I_2$로 확장하고, $I_3$, $\cdots$, 마지막으로 $I_m$으로 확장하는 것입니다. $m$번째 글자가 끝 문자라고 가정하면 $I_m$의 모든 리프 노드와 접미사가 일대일 대응이 되지만, $I_1, \cdots, I_{m-1}$은 그렇지 않습니다. 따라서 이들을 숨은 접미사 트리(implicit suffix tree)라고 부릅니다.

(※ “숨은 접미사 트리”는 제가 임의로 한 번역입니다.)

아래는 babnbo(바나나가 아닙니다!)의 모든 숨은 접미사 트리, 그리고 끝 문자가 붙은 최종 접미사 트리입니다. 마찬가지로 편의를 위해 부분문자열 전체를 레이블로 사용했습니다.

<I1root>  <I2root>  <I3root>
   |       /   \     /   \
   b      a    ba   ab   bab

 <I4root>      <I5root>        <I6rootI6root>
  /  |  \       /  |  \         /    |   |  \
abn  b   n   abnb  b   nb    abnbo   b  nbo  o
    / \           / \              / | \
  abn  n       abnb  nb       abnbo nbo o

   <rootrootrootroot>
   /     |   |   | \
abnbo$   b  nbo$ o$ $
       / | \
 abnbo$  |  o$
        nbo$

$I_i$를 $I_{i+1}$로 확장하는 것을 i+1번째 단계라고 합시다. 이 단계를 수행하려면, $j=1, \cdots, i+1$에 대해, $S[j..i]$를 $I_i$에서 찾고 그 위치에 글자 $S[i+1]$을 추가하면 됩니다. 이 과정을 j번째 확장이라고 합시다. ($j = i+1$일 때는 그냥 루트 노드에 있으면 됩니다.)

$S[j..i]$를 찾으려면, 루트에서 시작해서 한 글자씩 내려가면 됩니다. 한 노드의 끝에서 멈출 수도 있고, 숨은 노드에서 멈출 수도 있습니다. 그 다음 $S[i+1]$을 추가하는 것은 다음 규칙을 따릅니다.

규칙 1: 리프 노드의 끝에 도달했다면, 마지막 간선의 레이블에 $S[i+1]$을 덧붙입니다.
규칙 2a: 리프가 아닌 노드의 끝에 도달했는데 $S[i+1]$에 해당하는 자식이 없다면, 새로운 자식을 만들고 $S[i+1]$을 레이블로 둡니다.
규칙 2b: 숨은 노드에 도달했는데 다음 글자가 $S[i+1]$이 아니라면, 현재 지점에 새로운 노드를 끼워넣어 간선과 레이블을 둘로 나눈 다음, 그 새로운 노드에 또 새로운 자식을 만들고 $S[i+1]$을 레이블로 둡니다.
규칙 3: 위 세 규칙에 모두 해당하지 않는다면, $S[j..i+1]$이 이미 존재한다는 뜻입니다. 따라서 아무것도 하지 않습니다.

각 규칙의 예를 봅시다.

규칙 1: 3번째 단계의 1번째 확장
<I2root>    <I2root>
 /   \   ->  /   \
a   b[a]    a   ba[b]

규칙 2a: 6번째 단계의 5번째 확장
   <I5root>            <I5root>
   /   |   \           /    |  \
abnbo [b]   nbo ->  abnbo   b   nbo
      / \                 / | \
  abnbo nbo           abnbo | [o]
                           nbo

규칙 2b: 4번째 단계의 3번째 확장
<I3root>      <I3root>   <I3root>
 /   \     ->  /   |  ->  /   |
abn [b]abn    abn [b]    abn  b
                   |         / \
                  abn      abn [n]

규칙 3: 3번째 단계의 3번째 확장
[<I2root>]     <I2root>
  /   \    ->   /   \
 ab   bab      ab  [b]ab

시간 복잡도는 각각의 $j, i$에 대해 $O(m)$씩 걸리므로 총 $O(m^3)$입니다. 아니, 접미사 트라이를 만들고 압축하는 것만으로 $O(m^2)$이 되는데 무려 $O(m^3)$이라니요? 하지만 트리를 구축하는 과정을 이런 식으로 바꾼 덕분에 최적화의 길이 열리게 됩니다.

$O(m^2)$으로 최적화하기

$i$번째 단계의 $j$번째 확장에서 몇 번째 규칙을 적용했는지 표를 그려 봅시다. 2a와 2b는 둘 다 2로 표기했습니다.

 |1234567
-+-------
b|2       루트 노드는 리프가 아니라고 칩시다.
a|12
b|113
n|1122
b|11113
o|111122
$|1111112

1단계가 굉장히 많습니다. 게다가 이건 우연이 아닙니다!

만약 $i-1$번째 단계의 $j$번째 확장에서 규칙 1 또는 2가 적용되었다면, $i$번째 단계의 $j$번째 확장에서는 규칙 1이 적용됩니다. 다시 말하면, 한 번 리프 노드가 된 것은 영원히 리프 노드로 남습니다.
만약 $i$번째 단계의 $j-1$번째 확장에서 규칙 2가 적용되었다면, $j$번째 확장에서는 규칙 2 또는 3이 적용됩니다.
만약 $i$번째 단계의 $j-1$번째 확장에서 규칙 3이 적용되었다면, $j$번째 확장에서도 규칙 3이 적용됩니다.

따라서 거의 대부분은 규칙 1이나 3이 적용되고, 규칙 2는 최대 $m$번만 적용됩니다. 그리고 각 단계는 11...1122...2233...33의 형태를 띱니다. 이제 각 단계마다 규칙 1과 3을 통째로 $O(1)$에 적용할 수 있으면, 전체 알고리즘이 $O(m^2)$으로 최적화됩니다.

규칙 1을 최적화하려면, 각각의 레이블이 두 개의 정수 l, r에 대해 [l..r]로 표기된다는 사실을 기억합시다. 한 번 리프 노드는 영원히 리프 노드이므로, 리프 노드에 대해서만 r을 무한대로 둡시다. 그러면 이제 더 이상 레이블이 바뀌지 않습니다. 리프 노드가 몇 개 있었는지를 기억해 두고 각 단계에서 전부 건너뛰면 됩니다.
규칙 3을 최적화하려면, 규칙 3이 나오는 즉시 단계를 종료해버리면 됩니다. 어차피 3단계에서는 아무 일도 일어나지 않기 때문입니다.

$O(m)$으로 최적화하기

규칙 2를 최적화하려면 루트에서 시작해서 한 글자씩 내려가지 말고, 가운데 어딘가에서 시작해서 한 글자씩 내려가야 합니다. 리프가 아닌 노드 $v$ (숨은 노드는 고려하지 않습니다)의 접미사 링크 $s(v)$를 다음과 같이 정의합니다.

루트에서 $v$까지 내려갈 때 만나는 모든 레이블을 이어붙이면 $S$의 접두사 $S[1..t]$가 나옵니다. 이것을 $v$의 경로 레이블이라고 부릅시다.
이제 $s(v)$는 경로 레이블이 $S[2..t]$와 같은 노드입니다.

예를 들어, 이전 글에서 보았던 바나나를 다시 가져와 보면

      <root>
     /  |    \
    a banana$ na
   / \        | \
  na  $      na$ $
 /  \
na$  $

다섯 번째 줄의 맨 왼쪽 노드는 경로 레이블이 ana입니다. 이 노드의 접미사 링크는 경로 레이블이 na인 세 번째 줄의 맨 오른쪽 노드입니다.
그 노드의 접미사 링크는 경로 레이블이 a인 세 번째 줄의 맨 왼쪽 노드입니다.
그리고 그 노드의 접미사 링크는 루트 노드입니다.

만약 $j$번째 확장이 노드 $v$를 지나고 $k$글자 더 내려간 상태로 멈췄다면, $j+1$번째 확장은 $s(v)$를 지나고 $k$글자 더 내려간 상태로 멈출 것입니다. 따라서 $j$번째 확장이 마지막으로 거친 노드 $v$를 찾고, 그 노드에서 몇 글자 더 내려갔는지를 구하고, $s(v)$에서 $k$글자를 더 내려가면 됩니다.

그런데 이러면 두 가지 문제가 생깁니다.

접미사 링크가 있을까?

$s(v)$가 항상 존재할까요? 접미사 트리가 모든 부분문자열을 포함하니까 $S[2..i]$를 따라 내려갈 수는 있겠지만, 내려가서 도착한 곳이 숨은 노드인 경우는 없을까요? 다행히도 없습니다. 게다가, 어떤 확장에서 새로운 노드가 생기면 머지 않아 접미사 링크도 같이 생깁니다!

정리. $i$번째 단계의 $j$번째 확장에서 규칙 2b에 의해 리프 노드가 아닌 노드 $v$가 생길 경우, $s(v)$는 이미 존재하거나 $j+1$번째 확장에서 규칙 2b에 의해 만들어진다.

증명. 규칙 2b가 적용되었다는 것은, $S[j..i]$를 찾아서 도착한 곳이 숨은 노드이면서 다음 글자가 $S[i+1]$이 아니라는 것을 의미합니다. 실제 다음 글자를 $c$라고 합시다. 그러면 문자열 $S[j..i]+c$는 $S[..i+1]$의 부분문자열입니다. 따라서 $S[j+1..i]+c$도 $S[..i+1]$의 부분문자열이고, $j+1$번째 확장에서 $S[j+1..i]$를 찾아서 도착한 노드는 (1) 실제 노드이거나 (2) 다음 글자가 $c$인 숨은 노드입니다. 첫 번째 경우 그 노드가 바로 $s(v)$입니다. 두 번째 경우 규칙 2b에 의해 $s(v)$가 만들어집니다.

따라서 $v$에 접미사 링크가 없다면 다음 두 가지 케이스가 생깁니다.

$v$의 부모가 루트 노드인 경우. 이때는 그냥 거기서 쭉 내려가면 됩니다.
$v$의 부모가 루트 노드가 아닌 경우. 이 노드는 접미사 링크가 있을 것입니다. 따라서 $v$가 아니라 $v$의 부모로부터 몇 글자 내려갔는지를 센 다음, $v$의 부모의 접미사 링크로 이동해서 센 글자만큼 내려가면 됩니다. 그 후에 확장이 끝나면 새로운 노드가 생길 것이고, 그 노드는 $v$의 접미사 링크가 됩니다.

접미사 링크에서 내려가는 게 충분히 빠를까?

$k$가 너무 커서 한 글자씩 내려가는 게 여전히 비효율적인 경우는 없을까요? 그럴 수도 있습니다. 이 문제를 해결하려면 한번에 한 글자씩 내려가는 게 아니라 한 간선씩 내려가야 합니다. 어차피 내려가는 도중에는 노드를 추가할 일이 없으니 한꺼번에 내려가자는 것이죠.

정리. 루트에서 $v$까지 내려갈 때 필요한 간선의 개수를 $v$의 노드 깊이라고 하면, $v$의 노드 깊이는 $(s(v)$의 노드 깊이$) + 1$ 이하이다.

증명. 루트에서 $v$까지 내려갈 때 방문한 노드가 루트, $v_1, v_2, \cdots, v_k, v$라면, 루트에서 $s(v)$까지 내려갈 때 방문한 노드는 루트, ($s(v_1)$,) $s(v_2), \cdots, s(v_k), s(v)$입니다. ($s(v_1)$은 루트일 수도 있고, 그 경우에는 제외됩니다.)

노드로부터 내려가면 노드 깊이가 항상 증가하고, $s(v)$를 타면 노드 깊이가 감소할 수도 있습니다. 하지만 이 정리에 따르면 노드 깊이가 감소해봤자 1 감소하기 때문에, 한 단계를 통틀어서 노드 깊이가 증가하는 횟수는 총 $O(m)$밖에 되지 않습니다. 따라서 한번에 한 간선씩 내려가면 전체 단계가 $O(m)$으로 최적화됩니다.

드디어 $O(m)$ 시간복잡도로 접미사 트리를 만들었습니다!

응용

Ukkonen의 알고리즘이 어떤 식으로 작동하는지를 염두에 두면 접미사 트리로 더 많은 문제를 풀 수 있습니다.

서로 다른 부분문자열의 개수 동적으로 관리하기

BOJ 16907과 거의 유사합니다. 빈 문자열 $S$에서 시작해서, $S$의 맨 뒤에 문자 하나를 추가할 때마다 $S$의 서로 다른 부분문자열의 개수를 문자 당 $O(1)$에 구할 수 있습니다. 추가할 “때마다”라고 한 건, 쿼리가 온라인으로 주어져도 구할 수 있기 때문입니다.

이전 글에서, 서로 다른 부분문자열의 개수는 모든 레이블의 길이의 합이라고 했습니다. 루트밖에 없는 숨은 접미사 트리를 만듭니다. 문자를 추가하려면, 그 문자를 다음 단계로 두고 확장을 진행합니다. 규칙 1 또는 2가 적용될 때마다 길이의 합이 1 증가하므로 각 단계마다 길이의 합이 얼마나 늘어나는지 쉽게 계산할 수 있습니다.

맨 앞 글자를 삭제하면서 위 문제 풀기

마지막으로, BOJ 14436을 풀어봅시다. 심지어 이것도 온라인 쿼리로 $O(1)$에 풀 수 있습니다. 사실 두 달에 걸쳐 접미사 트리에 대한 글을 쓴 이유도 이 문제를 위해서였습니다.

문자열의 맨 앞 글자를 지울 때에도 접미사 트리를 관리할 수 있어야 합니다. 일단 접미사 트라이부터 생각해 봅시다. 접미사 트라이에서 맨 앞 글자를 어떻게 삭제할까요?

첫 번째 접미사에 해당하는 리프 노드를 지우면 됩니다. 그런데 여기서 끝내면 안 되는 게, 지운 노드의 부모에는 더 이상 아무 접미사도 들어있지 않을 수도 있습니다. 이 경우 부모도 지우고, 그 노드의 부모도 더 이상 아무 접미사도 없으면 지우고, 이걸 다른 접미사가 남아있는 노드에 도달할 때까지 해야 합니다. 노드에 다른 접미사가 남아있는 경우는 두 가지입니다.

노드에 다른 자식이 있을 경우.
노드가 리프 노드로 변하면서 새로운 접미사가 된 경우.

두 번째 경우는 무슨 뜻일까요? 문자열 aaa를 생각해 봅시다. (끝 문자는 없습니다.)

<root>
  |
  a
  |
  a
  |
  a

여기에는 리프 노드가 aaa 하나밖에 없지만, 사실 각 노드에 접미사 a, aa, aaa가 하나씩 대응됩니다. 이때 맨 앞 글자를 지우면 맨 밑에 있는 노드가 지워지는데, 바로 위에 있는 노드는 접미사 aa에 대응되므로 지우지 말아야 합니다. 이처럼 노드에 다른 자식이 없더라도 다른 접미사가 “숨어”있을 수는 있습니다.

노드에 접미사가 숨어있는지는 어떻게 알까요? 확장을 할 때 규칙 3이 적용되면 리프 노드가 생기지 않으므로, 이때 접미사가 숨게 됩니다. Ukkonen의 알고리즘은 규칙 3이 적용되자마자 단계를 끊고 이후의 확장을 하지 않으므로, 어디에 접미사가 숨어있는지를 일일이 표기할 수는 없습니다. 그 대신 접미사가 숨어있는 노드가 리프가 될 경우, 그 노드는 규칙 3이 최근 단계에서 처음으로 적용된 노드와 같다는 점을 관찰합시다. 왜일까요? 애초부터 첫 글자 없이 접미사 트리를 만들었다면 바로 그 노드가 리프가 되었을 것이기 때문입니다. 그러므로 규칙 3이 적용된 노드를 기억해 두고, 그 노드가 리프가 될 경우 노드 지우기를 멈추면 됩니다.

접미사 트리에서도 크게 다른 건 없습니다. 한번에 한 간선씩 통째로 지우되, 규칙 3이 적용된 (숨은) 노드가 중간에 있을 경우 딱 거기까지만 자르고 멈추면 됩니다. 간선이 완전히 지워졌을 경우 부모 노드는 자식이 하나만 남을 수도 있습니다. 그래서 “각 노드에서 두 갈래 이상으로 나뉜다”는 접미사 트리 조건이 깨지지만, 이 조건은 원래 공간 복잡도를 줄이기 위해 있었던 것이라서 상관 없습니다.

마치며

지금까지 접미사 트리의 정의, 알고리즘, 그리고 응용을 다뤄 보았습니다. 구현은 쉽지 않지만, 배우고 나면 문자열 문제에서 유용한 도구가 될 것으로 기대합니다. 실제로 이전 글에서 다뤘던 좋은 부분 문자열 같은 문제도 접미사 트리를 쓰면 간단한 트리 DP 문제가 됩니다. (접미사 배열 풀이가 어떤지를 생각해 보면…)

한편 선형 시간에 만들 수 있으면서 여러 문자열 문제를 해결할 수 있는 자료구조로 접미사 오토마톤이라는 것도 있습니다. 이에 대해서는 제가 모르지만, 접미사 트리와 접미사 오토마톤 사이에 깊은 연관이 있다고 하니 찾아보는 것도 좋을 것 같습니다.