접미사 배열에 새 패턴을 찾을 때 한 번의 이진 탐색으로 끝나지 않고 범위를 두 번 찾는 이유는 무엇인가요?

한 번의 이진 탐색으로 “어떤 일치가 존재하는가”를 확인하는 것과, 패턴을 접두로 갖는 모든 접미사의 구간을 얻는 것은 다른 질의입니다. 접미사 배열에서 패턴 P를 접미사와 비교할 때 P보다 사전순으로 작은 마지막 위치 다음을 lower_bound로 잡고, P를 접두로 갖는 마지막 위치 다음을 upper_bound로 잡습니다. banana의 suffix array는 [5,3,1,0,4,2], 즉 a, ana, anana, banana, na, nana 순서입니다. P=ana이면 배열 인덱스 [1,3)의 ana, anana가 모두 후보이고 원문 offset은 SA[1]=3, SA[2]=1입니다. 따라서 개수는 3-1=2입니다.

비교기는 완전한 문자열 동일성과 접두 일치를 나눠야 합니다. 접미사 a는 ana를 다 읽기 전에 끝나므로 작은 쪽이고, anana는 처음 세 글자가 ana와 같으므로 일치 구간 안에 들어갑니다. 이 규칙을 숫자 배열의 비교처럼 뭉뚱그리면 upper 경계에서 anana를 빠뜨리기 쉽습니다. 빈 패턴을 모든 위치에 허용할지 거절할지도 API에서 먼저 고정합니다. 이 예에서는 빈 패턴을 오류로 둡니다.

구현할 때는 경계를 반열린 구간으로 통일하면 l=0, r=n에서 시작해 불변식 앞쪽은 조건 불만족, 뒤쪽은 조건 만족을 유지하기 쉽습니다. 다만 두 번째 경계의 조건은 “패턴보다 크다”가 아니라 “패턴을 접두로 갖지 않는다”여야 합니다. ana와 anana가 둘 다 match인 이유가 바로 이 차이입니다. 반환 순서가 검색 순위가 아니라 원문 위치 순서여야 한다면 [1,3)의 3,1을 별도 정렬해야 하며, 배열을 찾는 비용과 결과 정렬 비용을 섞어 말하면 안 됩니다.