(알고리즘) 맨버 마이어스 알고리즘(접미사배열)
이 알고리즘은 O(n)시간안에 동작한다. 이것은 n개의 정수를 비교 정렬하는 것보다 빠르다.
이 알고리즘은 접미사들의 목록을 여러 번 정렬하는데, 매번 그 기준을 바꿉니다. 처음에는 접미사의 첫 한 글자만을 기준으로 정렬하고, 다음에는 접미사의 첫 두글자만을 기준으로 정렬하고, 그 다음에는 첫 네글자를 기준으로 정렬합니다. 이렇게 lgn번의 정렬을 하고 나면 우리가 원하는 접미사 배열을 얻게 되지요.
이렇게 정렬을 여러 번 하는데도 더 빠르게 동작하는 이유는 이전 정렬에서 얻은 정보를 이용해 두 문자열의 대소 비교를 O(1)할 수 있기 때문입니다.
첫 글자를 기준으로 접미사들을 정렬한 결과를 가지고 있다고 합시다. 각 접미사들을 첫 글자가 같은 것들끼리 그룹으로 묶고, 각 그룹마다 0부터 시작하는 번호를 매깁니다.
"mississipi"의 접미사를 정렬해 나가는 과정.
-->group[i]=S[i....]가 속한 그룹의 번호
이 알고리즘은 접미사들의 목록을 여러 번 정렬하는데, 매번 그 기준을 바꿉니다. 처음에는 접미사의 첫 한 글자만을 기준으로 정렬하고, 다음에는 접미사의 첫 두글자만을 기준으로 정렬하고, 그 다음에는 첫 네글자를 기준으로 정렬합니다. 이렇게 lgn번의 정렬을 하고 나면 우리가 원하는 접미사 배열을 얻게 되지요.
이렇게 정렬을 여러 번 하는데도 더 빠르게 동작하는 이유는 이전 정렬에서 얻은 정보를 이용해 두 문자열의 대소 비교를 O(1)할 수 있기 때문입니다.
첫 글자를 기준으로 접미사들을 정렬한 결과를 가지고 있다고 합시다. 각 접미사들을 첫 글자가 같은 것들끼리 그룹으로 묶고, 각 그룹마다 0부터 시작하는 번호를 매깁니다.
"mississipi"의 접미사를 정렬해 나가는 과정.
-->group[i]=S[i....]가 속한 그룹의 번호
댓글
댓글 쓰기