접미사 배열: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 →Manber-Myers 알고리즘: 설명 추가 |
잔글 →Manber-Myers 알고리즘: 문맥 수정 |
||
157번째 줄:
Manber-Myers 알고리즘은 정렬할 때 '''랭크'''라는 개념과 '''[[기수 정렬]]'''을 사용하여 시간복잡도를 줄인 알고리즘이다. 이 알고리즘은 접미사 배열을 구하는 다양한 알고리즘 가운데 프로그래밍 대회에서 자주 사용되는데, 시간복잡도가 더 작은 알고리즘은 짧은 시간 안에 구현하기 어렵기 때문이다.
이 알고리즘은 여러 단계의 정렬을 통해 전체 접미사를 정렬한다. Manber-Myers 알고리즘을 다음과 같이 개략적으로 설명할 수 있다.
1. 문자열 <math>S</math>의 접미사들을 첫번째 글자와 두번째 글자에 대해 사전순으로 정렬한다.
2. 정렬된 순서를 바탕으로 랭크를 부여한다.
| |||