티스토리 뷰

알고리즘 이론

Suffix Array, LCP Array

museop 2017. 2. 22. 22:48

Suffix Array



접미사 배열(suffix array)는 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로, 보통 각 접미사의 시작 위치를 저장하는 정수 배열로 구현된다. 길이가 \(n\)인 문자열의 접미사 배열을 만드는 가장 빠른 알고리즘은 \(O(N)\)만에 접미사 배열을 만든다고 한다. 하지만 프로그래밍 대회에서는 이 복잡한 알고리즘을 직접 구현하여 사용하기에는 어려워 보통 그 대안으로 적당히 구현하기 쉽고, 적당히 빠른 알고리즘을 대신 사용한다.


접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 각 접미사를 첫 한 글자로 정렬하고, 그 다음에 두 글자, 네 글자.. 로 \(log_2N\) 번 정렬하는 것이다. 각 접미사들이 서로 완전히 다른 문자열들이 아니라 두 접미사중 하나가 다른 하나를 포함하고 있기 때문에 이전 정렬에서 얻은 정보를 이용해서 두 접미사의 대소 비교를 \(O(1)\)에 수행한다.


구현

접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 다음과 같이 구현할 수 있다.


위의 알고리즘에서는 정렬 시에 보통의 \(O(Nlog_2N)\) 알고리즘을 사용하지만, 선형 시간복잡도를 가지는 계수 정렬(Counting Sort)를 이용하면, 아래와 같이 접미사 배열을 만드는 총 시간복잡도를 \(O(Nlog_2N)\)로 줄일 수 있다.  



Longest Common Prefix Array



접미사 배열과 함께 자주 사용되는 것이 있는데 바로 LCP 배열이다. Longest Common Prefix, 말 그대로 가장 긴 공통 접두사를 의미하는데, 여기서 말하는 LCP 배열은 (사전순으로 정렬되어 있는) 접미사 배열에서 이전 접미사와의 최장 공통 접두사의 길이를 저장한다. 문자열, 그 문자열의 접미사 배열, 그리고 LCP 배열의 관계는 아래 표를 보면 이해하기가 쉽다.



 i

suffixArray[ i ] 

suffix 

LCP[ i ] 

 0

 5

 a

 

 1

 3

 ana

 1

 2

 1

 anana

 3

 3

 0

 banana

 0

 4

 4

 na

 0

 5

 2

 nana

 2


LCP 배열은 접미사 배열에서 사전상으로 인접한 두 접미사의 최장 공통 접두사의 길이를 하나 하나 세면 되지만, 이 방식은 \(O(N^2)\)의 시간이 소요되는 방식이다. 이 LCP 배열을 계산하는 보다 효율적인 \(O(N)\) 알고리즘이 존재하는데 그 핵심 아이디어는 접미사 배열을 계산할 때와 마찬가지로 한 접미사는 다른 접미사의 접미사라는 점을 이용하여 중복된 계산을 줄이는 것이다.



 i

suffixArray[ i ] 

suffix 

LCP[ i ] 

 0

 5

 a

 

 1

 3

 ana

 1

 2

 1

 anana

 3

 3

 0

 banana

 0

 4

 4

 na

 0

 5

 2

 nana

 2



위의 접미사 배열에서 인접한 접미사 "ana"와 "anana"의 LCP는 3이라는 것을 계산했다고 하자. 그 후에 "na", "nana"의 LCP를 계산하려고 할 때, 한 가지 사실을 알 수 있다. 이미 "ana"와 "anana"의 LCP는 3이라고 계산해두었기 때문에 앞의 a가 없는 "na"와 "nana"의 LCP는 최소 2라는 사실이다. (보다 자세한 내용은 여기를 참고하면 될 것 같다.)


즉, S[i..], 그리고 S[i..]와 사전상으로 인접한 접미사(접미사 배열상 바로 이전 접미사)와의 LCP를 \(m\)이라고 하면, S[i+1..], S[i+1..]와 사전상으로 인접한 접미사의 LCP는 최소 \(m-1\) 이므로 이 부분은 중복하여 계산하지 않아도 된다.


구현



예제


참고 자료


'알고리즘 이론' 카테고리의 다른 글

Modular Arithmetic  (0) 2017.03.18
탐색 (Searching)  (0) 2017.03.06
Counting Sort, Radix Sort  (0) 2017.02.23
트리의 지름 (Diameter of Tree)  (0) 2017.02.20
KMP Pattern Searching  (0) 2017.02.20
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/02   »
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
글 보관함