두 임의 suffix의 LCP를 인접 LCP 배열의 RMQ로 바꿀 때 구간 끝은 어떻게 정하나요?

먼저 LCP 배열의 저장 정의를 고정해야 합니다. 여기서는 LCP[r]=lcp(SA[r-1],SA[r])로 둡니다. 두 suffix의 rank를 swap해 r1<r2로 만든 뒤, 두 suffix 사이에 있는 인접 경계는 r1+1, r1+2, ..., r2입니다. 그러므로 답은 LCP[r1+1..r2]의 최솟값입니다. rank 2와 5를 비교한다면 rank 2-3, 3-4, 4-5의 세 경계인 LCP[3],LCP[4],LCP[5]를 RMQ에 넣습니다. LCP[2]까지 넣으면 rank 1과 2 사이의 unrelated한 경계를 포함합니다.

banana의 suffix array [5,3,1,0,4,2]에서 인접 LCP는 LCP[1..5]=[1,3,0,0,2]입니다. rank 1과 2는 LCP[2]=3이므로 ana와 anana의 LCP 3을 얻습니다. rank 2와 5는 [3,5]의 최솟값 0이므로 anana와 nana의 공통 접두는 0입니다. 같은 rank이면 RMQ 구간이 비어 있으므로 호출하지 않고 suffix 길이 n-SA[r]를 반환합니다. rank가 역순으로 들어오는 것도 먼저 정렬합니다.

왜 최솟값인지도 함께 말해야 합니다. 모든 인접 LCP가 적어도 k면 그 순서 사이의 suffix들이 첫 k글자를 공유해 양 끝도 공유합니다. 반대로 어느 경계 하나가 k보다 작으면 그 경계에서 두 그룹이 갈라지므로 양 끝이 더 긴 공통 접두를 가질 수 없습니다. sparse table은 정적 배열에서 빠른 조회를 주지만 전처리 메모리를 쓰고, segment tree는 보통 O(log n) 조회를 선택합니다. 자료구조 선택은 구간 끝의 정확성과 별개입니다.

따라서 RMQ 호출부는 if r1==r2를 먼저 처리한 뒤, left=r1+1, right=r2라는 논리적 포함 범위를 선택한 구조의 API로 변환해야 합니다. 예를 들어 반열린 RMQ라면 [r1+1,r2+1)로 넘깁니다. LCP에 0번 dummy를 넣었는지, 실제 경계가 1번부터 시작하는지도 같은 테스트에서 확인해야 합니다. rank 0과 마지막 rank, 같은 suffix를 각각 넣어 빈 구간·배열 끝 접근이 없음을 검증하는 것이 숫자 하나를 확인하는 것보다 중요합니다.