(알고리즘) Manver-Myers 알고리즘(접미사 배열)
접미사 배열은 주어진 문자열에 대한 모든 접미사를 나열한 다음 알파벳순으로 정렬하는 배열입니다. 일반적으로 접미사 배열을 만드는 절차는 다음과 같습니다. 문자열의 모든 접미사를 생성합니다. 생성된 접미사를 첫 글자로 정렬합니다. 이후 정렬 기준은 처음부터 2번째 문자, 3번째 문자 등으로 증가하며 문자열의 최대 길이인 n번째 문자로 변경하여 정렬한다. 위 과정에 따르면 1회 정렬하는데 $O(n log n)$의 시간이 소요되며 … Read more