컴퓨터 과학에서 접미사 배열(Suffix Array)란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. S = S[0]S[1]...S[n-1] 이라는 문자열이 있다고 하자. 이때 S[i,j] 는 i번째 문자부터 j번째 문자 까지 S의 부분 문자열이라고 하자. 문자열 S에 대한 접미사 배열 A는 S의 접미사들을 사전식 순서로 정렬 했을 때 접미사의 시작 위치를 저장한 정수 배열이다. 즉 A[i] 에 저장 된 내용은 사전순으로 i 번째인 S의 접미사의 시작 위치이다. 다시 말하면 문자열 S의 길이를 n이라고 할 때 , 0