다양한 문자열 문제를 해결하기 위해서는 접미사 배열(suffix array) 자료구조를 이해해야한다. 접미사 배열은 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해 둔 것이다. 이 말 그래도 모든 접미사들을 문자열 배열에 저장하면 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에, 대개 접미사 배열은 각 접미사의 시작 위치를 담는 정수 배열로 구현된다. 예를 들면 아래 표는 문자열 "alohomora"의 접미사 배열 A[]와 각 위치에서 시작하는 접미사들을 보여준다. i A[i] S[A[i] ..] 0 8 a 1 0 a l o h o m o r a 2 3 h o m o r a 3 1 l o h o m o r a 4 5 m o r a 5 2 o h o m o r a 6 4 o m o r a 7 6 ..