DC3 (Skew)

1mod 3 분류#

길이 n인 문자열의 위치를 mod 3으로 세 그룹으로 나눈다.

• B_i = { j : j mod 3 = i } (0 ≤ i ≤ 2)

B₁₂ = B₁ ∪ B₂, |B₁₂| ≤ ⌈2n/3⌉.

2B₁₂ 정렬#

각 B₁₂ 위치 i에서 시작하는 삼중자 t_i = (S_i, S_i+1, S_i+2)를 기수 정렬로 정렬한다. 삼중자가 모두 고유하면 B₁₂의 순서가 확정된다.

중복이 있으면 각 삼중자에 순위(이름)를 부여해 새 문자열 r₁₂를 만들고, r₁₂에 대해 DC3를 재귀 호출한다.

• r₁₂의 앞 n₁개: B₁ 위치 삼중자 t₁, t₄, t₇, ⋯ 의 rank
• r₁₂의 뒤 n₂개: B₂ 위치 삼중자 t₂, t₅, t₈, ⋯ 의 rank

|r₁₂| ≤ ⌈2n/3⌉이므로 T(n) = T(2n/3) + O(n) → T(n) = O(n). 재귀 결과로 B₁₂ 전체의 정렬 순서와 각 위치의 rank가 확정된다.

3B₀ 정렬#

i ∈ B₀이면 i+1 ∈ B₁이므로 rank(i+1)은 B₁₂ 정렬에서 이미 알고 있다. 따라서 B₀ 위치는 (S_i, rank(i+1)) 쌍으로 기수 정렬할 수 있다.

4병합#

정렬된 B₀와 B₁₂를 병합한다. B₀ 위치 a와 B₁₂ 위치 p의 비교는 O(1)이다.

p ∈ B₁: a+1 ∈ B₁, p+1 ∈ B₂. 둘 다 B₁₂이므로 rank를 안다.

suf(a) < suf(p) ⇔ (S_a, rank(a+1)) < (S_p, rank(p+1))

p ∈ B₂: a+2 ∈ B₂, p+2 ∈ B₁. 둘 다 B₁₂이므로 rank를 안다.

suf(a) < suf(p) ⇔ (S_a, S_a+1, rank(a+2)) < (S_p, S_p+1, rank(p+2))

비교가 O(1)이므로 병합 전체가 O(n).

5참고 문헌#

• Kärkkäinen, J., Sanders, P., & Burkhardt, S. (2006). Linear work suffix array construction. Journal of the ACM, 53(6), 918–936.