접미사를 순서대로 배열하기
접미사는 문자열의 어느 위치에서 시작해 마지막 문자까지 이어지는 부분이다. 길이가 n인 문자열에는 빈 접미사를 제외하면 n개의 접미사가 있다. 접미사 배열은 시작 위치 자체의 크기 순서가 아니라 그 위치에서 읽히는 문자열의 사전식 순서를 기록한다.
짧은 문자열의 예
문자열 cab의 접미사는 0에서 시작하는 cab, 1에서 시작하는 ab, 2에서 시작하는 b다. 알파벳 순서로 정렬하면 ab, b, cab이므로 접미사 배열은 [1,2,0]이다. 각 원소는 접미사의 길이나 등장 횟수가 아니라 원래 문자열에서의 시작 위치다.
구축 비용을 구별하기
접미사를 실제 문자열로 만들어 비교 정렬하면 한 번의 비교에도 긴 접두사를 읽어야 할 수 있다. 따라서 비교 횟수가 O(n log n)이라고 해서 전체 계산이 곧 O(n log n)인 것은 아니다. 대표적인 두 배 확장 방식은 이미 계산한 순위 쌍을 사용하며, 계수 정렬 등을 결합하면 O(n log n)에 구축할 수 있다.
검색과 공통 접두사
정렬된 접미사에서 특정 패턴으로 시작하는 접미사들은 연속한 구간에 놓인다. 이를 이용해 패턴이 나타나는 범위를 찾을 수 있다. 인접 접미사의 최장 공통 접두사 길이를 저장하는 LCP 배열을 함께 사용하면 반복 부분이나 서로 다른 부분 문자열의 수를 분석하는 데 도움이 된다.