문자열 - 접미사 배열

[1. 개요]

접미사 배열은 굉장히 다양한 문자열 문제를 푸는 데 사용 할 수 있으며, 

이 자료구조는 아래와 같은 데이터를 표현한다.

• 어떤 문자열 S 의 모든 접미사를 사전순으로 정렬
• 이때, 배열에 실제로 저장하는 것은 각 접미사의 시작 위치이다.
• 예를들어, A[i] = 7 일 때, S[7...] 을 표현하는 것이다.

그래서 이 자료구조를 이용하여 아래와 같은 문제를 해결 할 수 있다.

• 문자열 검색
• 찾고자 하는 "문자열 N" 이 "문자열 H" 의 어떤 접미사의 접두사라는 점을 이용한다.
• H 의 접미사 배열을 이진 탐색하여, 문자열 N 이 출현하는 위치를 찾을 수 있다.

---

[2. 접미사 배열 생성]

접미사 배열을 생성하는 가장 단순한 방법의 시간복잡도는 O(n^2logn) 으로,

일반적인 경우에서는 이 보다 더 빠르다.

다만, 모든 형태의 입력에서는 그 실행시간을 보장하지 않으며,

이 보다 빠른 알고리즘이 있지만, 여기서는 맨버-마이어스 알고리즘을 정리하도록 한다.

---

[3. 맨버-마이어스 알고리즘]

알고리즘의 핵심 - 1

• 접미사들의 목록을 여러번 정렬하는데,
• 매번 그 기준을 아래와 같이 바꾼다.
• 처음에는 첫 한글자 만을 기준으로 정렬하고,
• 이전 단계의 두배만큼의 글자를 기준으로 정렬해나간다.
• 이렇게, logn 번 정렬하면 원하는 접미사 배열을 얻게 된다.
• 여기서, 두 문자열의 비교는 O(1) 에 할 수 있다.

알고리즘의 핵심 - 2

• 이전 단게 정렬에서 얻은 정보를 이용하여 두 문자열을 비교하기 때문이다.
• 자세히, 
• 첫 n 글자를 기준으로 정렬하고나면, 첫 n 글자가 같은 것들끼리 그룹으로 묶을 수 있다.
  => group[i] : S[i...] 가 속한 그룹 번호를 저장
  => 그룹 번호는 보통 0부터 serial 하게 증가
• 그 다음 단계에서, 첫 2n 글자를 기준으로 정렬 할 때는, 이전 단계에서 그룹 정보를 사용한다.
• 다른 그룹이면, 첫 n 글자가 다르며, 그룹 번호의 대소 비교를 이용하여 어느 접미사가 앞서는지 알 수 있다.
• 같은 그룹이면, 첫 n 글자가 같은 것이며, 이 때는 뒤 n 글자의 그룹을 비교하여 어느 접미사가 앞서는지 알 수 있다.

결국, 이 알고리즘을 사용하면, O(n(logn)^2) 의 시간복잡도로 접미사 배열을 생성 할 수 있다.

---

[4. 구현]

모든 접미사들에 대해서,

• 첫 t 글자에 대해 정렬하고,
• group 을 만들도록 한다.
• 위 과정이 t 글자가 원 문자열의 길이 이상이 될 때까지 반복한다.