Suffix Array와 Index Tree

1. Suffix Array 란?

해석하면 접미사 배열로 다양한 문자열 문제들을 해결할 수 있는 매우 강력한 자료구조입니다.

문자열(Array)의 접미사(Suffix)를 사전순으로 정렬한 배열이고 보통 문자열 검색이나 전문 검사 등에 쓰입니다.

Suffix Array를 이용한 대표적인 문제론 여러분들의 두뇌를 괴롭힐 LCP Array(Longest Common Prefix Array)가 있습니다.

​

위의 그림은 banan 라는 문자열을 Suffix Array로 나타낸 경우입니다.

Suffix Array는 완전 탐색보다는 조금 나은 수준으로 O(N^2)의 공간복잡도를 가집니다.

​

그럼에도 왜 힘들게 구현하여 쓰는가.

바로 이런식으로 몇 번째 접미사인지 나타내는 정수 i만 가지는 정수형 자료 구조 형태를 갖기 때문입니다.

​

2. Index Tree 란?

간단하게 IndexTree-Segment Tree에 대하여 설명하도록 하겠습니다.

위 그림처럼 Index Tree 특징은 부모 노드의 값은 자식 노드 값들의 합이고,리프 노드는 A 배열의 각 요소들이라는 것입니다.

​

Index Tree를 사용하는 이유는 계속 바뀌는 A 배열의 부분 합을 구할 때, 부분 합을 트리구조에 저장함으로서 O(logN)의 속도로 A 배열의 부분 합을 빠르게 구해주기 때문입니다.

​

N이 10일때의 index tree의 인덱스 값

아무튼 A 배열의 크기가 N이라 하면, 리프 노드의 개수는 N이 되므로 이 트리의 높이 H는 [logN]이 되고, 배열의 크기는 2^(H+1)입니다.