티스토리 뷰

공부

Suffix Array와 LCP

전명우 2014.08.14 15:01

Suffix Array (접미사 배열)


Suffix Array(韓: 접미사 배열)은 어떤 문자열의 suffix(접미사)들을 사전순으로 나열한 배열을 의미한다. 문자열 관련된 문제에서 자주 쓰이는 방법이다.


예를 들어, 문자열 $S = banana$가 있다고 하자. 문자열 $S$의 접미사들은 아래와 같다.


suffix

i

 banana

1

anana

2

nana

3

ana

4

na

5

a

6


문자열 $S$의 접미사 배열은 아래와 같다.


suffix

i

a

6

ana

4

anana

2

banana

1

na

5

nana

3


접미사 배열에서 문자열을 배열로 가지고 있으면 공간복잡도가 $O(N^2)$이기 때문에 접미사를 나타내는 정수 $i$를 가지고 있는다. 즉, "banana"의 접미사 배열은 [6,4,2,1,5,3] 이다.


접미사 배열을 구하는 가장 쉬운 방법은 단순히 정렬하는 방법이다. 문자열의 사전순 비교에 드는 시간은 $O(N)$이며, 항이 $N$개 있으므로, 정렬하는 시간복잡도는 $O(N^2 \lg N)$이다.


접미사 배열을 구하는 빠른 알고리즘 중 가장 알려진 알고리즘은 $O(N \lg N)$이다. Pang Ko와 Srinivas AluruJuha, Petuha Kärkkäinen와 Peter Sanders 등등 $\Theta(N)$만에 구하는 알고리즘도 개발되었지만, 경시에서 사용될 만큼 통용되진 않았다. 경시 문제에서는 $O(N \lg N)$ 보다 빠른 시간복잡도를 요구하는 문제는 안나온다고 볼 수 있다.


접미사 배열을 $O(N \lg N)$만에 구하는 방법은 길이를 1, 2, 4, 8, … 로 증가하면서 counting sort하는 방법이다. 자세한 설명은 코드를 게시하는 것으로 대신하겠다.



LCP (Longest Common Prefix)


접미사 배열 자체만으로 해결할 수 있는 문제는 거의 없다. 접미사 배열과 함께 중요한 개념인 LCP (Longest Common Prefix)를 소개하겠다. LCP의 뜻은 가장 긴 공통 접두사로 일반적으로 그 길이에 의미가 있다. 대부분의 상황에서 Suffix Array에 쓰이는 개념이라고 볼 수 있다.


lcp[i]는 접미사 배열의 $i$번째 접미사와 $i-1$번째 접미사의 가장 긴 공통 접두사의 길이라고 정의된다. "banana"의 접미사 배열과 lcp 값은 아래와 같다.


suffix

i

lcp

a

6

 x

ana

4

 1

anana

2

 3

banana

1

 0

na

5

 0

nana

3

 2


이 때, $1 < i \leq N$인 모든 $i$에 대해 lcp[i] 값을 계산하는 시간복잡도가 $O(N)$인 알고리즘이 있다. 코드는 아래와 같다.



연습 문제: BOJ 9248

코드 보기


끝으로, 접미사 배열과 LCP를 이용하여 해결 할 수 있는 문제가 굉장히 많다.

예) 최장 공통 부분 문자열, 부분문자열의 가장 큰 등장값

'공부' 카테고리의 다른 글

Majority Vote Algorithm  (1) 2016.06.23
Grundy Number  (0) 2014.11.13
Suffix Array와 LCP  (11) 2014.08.14
Manacher's Algorithm  (0) 2014.08.13
중국인의 나머지 정리와 확장 유클리드 알고리즘  (0) 2014.07.25
고속 푸리에 변환 (Fast Fourier Theorem, FFT)  (4) 2014.07.25
댓글
  • 프로필사진 rlatkddn212 정리 잘해주셔서 감사해요.

    ㅎㅎ 제가 이해 한게 맞다면 LCP 부분에서 값이 틀린것 같아요?..

    x13022 라고 되어있는데 x13002 아닐까요?
    2014.11.04 18:05 신고
  • 프로필사진 전명우 확인이 늦어서 죄송합니다. 즉시 수정하겠습니다. 2014.11.10 02:12 신고
  • 프로필사진 skawlsdlf51 ㅎㅎ 2014.11.04 20:00 신고
  • 프로필사진 yswon SuffixArray를 얻는 코드에서 x와 y의 정의가 뭔지 질문드려도 될까요? 2016.04.10 14:34 신고
  • 프로필사진 SA공부하고있는사람 저도 이게 좀 궁금합니다.
    문자열 S가 "banana" 일때를 예를들어
    매 반복마다 x,y,SA 의 변화를 적어가며
    파악해보려했지만 정확하게 파악하기가 쉽지가않네요.
    2016.12.17 10:42 신고
  • 프로필사진 깜장호랭 좋은 코드를 발견하여, 살펴 보고 분석하고 있습니다. x가 rank입니다. 여기서의 index가 S의 index이고 해당하는 lcp 구할 때 rank에 해당합니다. 즉, i로 시작하는 suffix의 rank값이 x에 저장됩니다. SA는 이것의 inverse라고 보시면 됩니다. order라고 할까요? 'banana' 스트링의 SA값은 6,4,2,1,5,3이 될텐데요. 즉, 테이블의 값이 됩니다. 저는 이 코드들을 0으로 시작하는 배열로 변경하여 사용하고 있습니다. 2017.10.13 14:38 신고
  • 프로필사진 전명우 대신 답해주셔서 감사합니다. 2017.11.03 18:06 신고
  • 프로필사진 학생 for (int len=1,p=1;p<N;len<<=1,m=p){
    에서
    <<= 뜻이 뭐에요 ..
    2016.08.08 18:49 신고
  • 프로필사진 전명우 비트연산자 입니다. 2016.08.17 05:22 신고
  • 프로필사진 니켈 혹시 LCP 구하는부분에서
    S[i+k]==S[j+k];k++ 이부분이 왜 상수시간안에 해결될 수 있는지 이해가 안되네요 ㅠㅠ
    최악의 경우 O(N) 이 걸릴것 같은데... 혹시 이부분에 대해서 설명해주실 수 있으신가요?
    2018.07.02 12:29 신고
  • 프로필사진 전명우 Line 15에 있는 for문이 상수시간에 돌아간다는 말이 아닙니다. Line 14, 15에 있는 이중for문의 총 시간복잡도가 O(N)이라는 말입니다. 이는 i+k의 값이 시간이 지남에 따라 절대 감소하지 않는다는 것과 i+k의 값이 N보다 커지지 않아 k++이 되는 횟수가 최대 N임을 통해 증명 가능합니다. 2018.07.27 16:15 신고
댓글쓰기 폼