[Algorithm] 20 문자열 - 7
접미사 배열 만들기 - 멘버 마이어스 알고리즘
- 우리가 정렬하는 문자열들이 한 문자열의 접미사라는 점을 이용해 수행 시간을 낮추는 방법
- 이 알고리즘은 접미사들의 목록을 여러 번 정렬하는 데 매번 그 기준을 바꾼다.
- 처음에는 접미사의 첫 한 글자만을 기준으로 정렬
- 다음에는 접미사의 첫 두 글자를 기준으로 정렬
- 그 다음에는 접미사의 첫 네 글자를 기준으로 정렬
- 이렇게 log N 번의 정렬을 하고 나면 원하는 접미사 배열을 얻을 수 있다.
- 정렬을 여러 번 하는데도 더 빠르게 동작하는 이유는 이전 정렬에서 얻은 정보를 이용해 두 문자열의 대소 비교를 O(1)에 할 수 있기 때문이다.
예) 문자열 “mississipi”
첫 한 글자를 기준으로 접미사들을 (abc 오름차순) 정렬한 결과를 가지고 있다고 할 때, 각 접미사들을 첫 글자가 같은 것들끼리 그룹으로 묶고, 0부터 시작하는 번호를 매긴다.
| group[0] | group[1] | group[2] | group[3] |
|---|---|---|---|
| ississipi | mississipi | pi | ssissipi |
| issipi | sissipi | ||
| ipi | ssipi | ||
| i | sipi |
group[0] = i로 시작하는 접미사들
group[1] = m으로 시작하는 접미사들
group[2] = p로 시작하는 접미사들
group[3] = s로 시작하는 접미사들
멘버 마이어스 알고리즘 구현
다음과 같은 배열 group [] 을 만든다.
접미사들을 맨 앞에서부터 순회하면서 각 접미사에 그룹 번호를 부여한다.
첫 접미사에는 항상 그룹 번호 0번을 부여한다.
그 이후부터는 이전 접미사와 첫 글자가 같으면 이전 접미사의 그룹번호를 부여한다.
아니라면 이전 접미사의 그룹 번호에 1을 더한 번호를 부여한다.
첫 t글자를 기준으로 만든 group[] 이 있으면 두 접미사 S[i…], S[j…] 중 첫 t글자를 기준으로 어느 쪽이 더 앞에 오는지를 쉽게 알 수 있다. group[i] 와 group[j] 중 어느 쪽이 더 작은지를 확인하면 된다.
S[i…], S[j…] 중 첫 2t글자를 기준으로 어느 쪽이 사전에서 앞에오는지도 상수 시간에 판단할 수 있다.
어떻게?
S[i…], S[j…] 가 주어질 때, 우선 첫 t글자를 비교한다.
만약 이들이 서로 다르다면 나머지도 볼 필요 없이 어느 쪽이 앞에 오는지 결정할 수 있다.
만약 두 접미사가 같은 그룹에 속한다면? S[i+t…], S[j+t…] 의 첫 t 글자를 서로 비교하면 된다.