접미사 배열: 두 판 사이의 차이

 

랭크 기반 정렬을 수행하기 전에 우선 문자열<math>S</math>의 접미사들을 첫번째 자리와 두번째 자리에 대해 사전순으로 정렬해준다. 이때 해당하는 자리에 문자가 없으면 모든 문자보다 앞서도록 처리한다. 작업을 수행하고 나면 앞의 두 자리에 대해 정렬되어있게 된다. '''모든''' 접미사 <math>S[i,n]</math>에 대해 앞의 두 자리에 대해 정렬이 되어있으므로 또다른 접미사인<math>S[i+2,n]</math>에 대한 순서도 알 수 있다. 이 순서를 다음 랭크로 정하고 이전의 두 자를 비교한 정보를 더하면 접미사들을 네 글자까지 정렬한 결과를 알 수 있다. 이때 첫번째, 두번째 글자에 대한 정보는 필요없고 정렬된 순서만 필요하므로 두개의 숫자를 압축할 수 있다.

 

==== 기수 정렬의 구체적인 방법====