Suffix Array · LCP

SA는 서로 다른 시작 인덱스 $0,\ldots ,N-1$의 순열이다. $\operatorname{rank}[\mathrm{SA}[r]]=r$로 정의하면 각 시작 위치에 정확히 한 순위가 대응한다. $i=\mathrm{SA}[r]$를 대입하면 $\mathrm{SA}[\operatorname{rank}[i]]=i$가 바로 따른다. 두 접미사의 사전순 비교는 두 rank의 비교와 동치이다. 단, Doubling 중간 단계의 동치류 번호에는 이 역함수 관계를 적용하지 않는다.

∎

불변식. 길이 k 단계의 rank는 각 접미사의 앞 $\min(k,|S_i|)$글자에 대해 동치와 사전순을 보존한다. 즉 두 rank가 같을 필요충분조건은 비교 대상 문자열이 같음이고, rank의 대소는 그 문자열의 사전순과 일치한다.

기초. $k=1$에서 문자의 순위로 정의하면 불변식이 성립한다. C++ 구현은 문자 코드 자체를 초기 rank로 사용한다. 연속된 번호가 아니어도 순서와 동치를 보존하므로 충분하다.

귀납 단계. 앞 2k글자를 비교할 때 먼저 앞 k글자를 비교하고, 같으면 다음 k글자를 비교한다. 귀납 가정에 의해 이는 $(\operatorname{rank}[i], \operatorname{rank}[i+k])$의 사전순 비교와 같다. 뒷부분이 없을 때 −1을 사용하면 짧은 문자열이 먼저 온다는 규칙도 보존된다. 정렬 후 같은 키에 같은 번호, 다른 키에 증가한 번호를 부여하면 2k 단계의 불변식이 성립한다.

길이가 k보다 짧을 때도 성립하는가. 첫 블록이 길이 k 미만이면 그 접미사는 이미 끝났으므로 둘째 블록은 없다. 따라서 짧은 첫 블록이 다른 첫 블록의 proper prefix인 경우에도 전체 비교에서 반드시 먼저 온다. 첫 블록이 같고 길이 k이면 둘째 블록 비교로 넘어가며, 비어 있는 둘째 블록은 −1로 모든 비어 있지 않은 블록보다 앞선다. 그러므로 모든 경계 경우에서 쌍 비교가 $W_{2k}$의 동치와 순서를 모두 보존한다.

모든 rank가 다르면 접미사들의 순서가 이미 비교된 부분에서 결정됐으므로 나머지 문자와 무관하게 전체 순서도 확정된다. 그렇지 않아도 $2k\ge N$이면 모든 접미사를 끝까지 비교하므로 정렬이 완료된다. 단계 수는 $O(\log N)$이다. $N\le 1$은 자명한 경우이다.

∎

A와 C가 길이 h의 접두사 P를 공유하고 $A\le B\le C$라고 하자. B가 P를 공유하지 않는다고 가정한다. 첫 불일치에서 B의 문자가 작으면 $B<A$, 크면 $B>C$가 된다. B가 h글자 이전에 끝나는 경우에도 B는 A의 proper prefix이므로 $B<A$이다. 모두 가정에 모순이다. 따라서 B도 P를 공유한다. 즉 특정 접두사를 갖는 접미사들은 SA의 연속 구간을 이룬다.

∎

i의 사전순 바로 이전 접미사를 $S_{j}$라 하고 $h=\operatorname{lcp}(S_{i},S_{j})$라 하자. $h\le 1$이면 다음 위치에서 재사용하는 길이는 0이므로 자명하다. $h\ge 2$이면 $S_{i}$와 $S_{j}$의 첫 문자가 같고, 이를 제거한 $S_{i+1}$과 $S_{j+1}$은 $h-1$글자를 공유한다.

같은 첫 문자를 제거해도 사전순은 보존되므로 $S_{j+1} < S_{i+1}$이다. $S_{i+1}$의 바로 이전 접미사를 Sₚ라 하면 $S_{j+1} \le S_{p} < S_{i+1}$이다. 보조정리 3에 의해 Sₚ도 동일한 $h-1$글자를 공유한다. 따라서 다음 비교는 최소 $h-1$까지 이미 일치함이 보장된다.

$h\ge 2$이면 $i+1$과 $j+1$ 모두 N보다 작으므로 두 접미사는 배열에 실제로 존재한다. 또한 $S_{j+1}$이 $S_{i+1}$보다 작으므로 이 경우 $S_{i+1}$의 순위가 0일 수 없다. $h\le 1$이면 하한이 0이므로 이전 이웃의 존재 여부와 무관하게 안전하다. “비교 상대가 반드시 $j+1$이다”라는 더 강한 주장은 필요하지 않다.

이 하한부터 문자가 같은 동안 증가시키고, 불일치 또는 문자열 끝에서 멈추면 정확한 LCP를 얻는다. $\operatorname{rank}=0$이면 이전 접미사가 없으므로 $\mathrm{LCP}[0]=0$으로 정의하고 h를 0으로 초기화한다. 모든 i를 순회하고 rank가 순열이므로 모든 LCP 원소를 정확히 한 번 계산한다.

반복문 불변식. i번째 반복 진입 시 h는 현재 비교 상대와의 실제 LCP 이하이다. $i=0$에서는 $h=0$이므로 성립하고, 위 보조 성질이 다음 반복에 대한 귀납 단계를 보장한다. while에서는 앞 h글자의 동일성을 유지하며, 멈춘 이유가 불일치 또는 한쪽 문자열의 종료이므로 얻은 h는 하한에 그치지 않고 정확한 최댓값이다.

∎

h가 증가할 때마다 성공한 문자 비교가 한 번 발생한다. 일반 반복 끝에서의 감소는 최대 1이므로 감소량 합은 N 이하이다. $\operatorname{rank}=0$인 위치는 한 번뿐이며 이때의 초기화로 발생할 수 있는 추가 감소량도 N 이하이다. h는 0에서 시작하고 항상 $0\le h\le N$이므로 총 증가량은 $O(N)$이다.

각 i에서 마지막 불일치·경계 검사와 나머지 연산은 $O(1)$이므로 전체 시간은 $O(N)$이다. rank와 LCP가 길이 N인 배열이므로 추가 공간도 $O(N)$이다. 매 위치마다 h를 0으로 바꾼 뒤 비교하면 이 분석이 성립하지 않으며, 반복 문자열에서 $O(N^{2})$이 될 수 있다.

증가 총량을 I, 감소 총량을 D, 마지막 값을 H라 쓰면 $0+I-D=H$이므로 $I=D+H$이다. $D\le 2N, H\le N$에서 $I\le 3N$을 얻는다. 이 상계는 느슨하지만 선형임을 보이기에 충분하다. 안쪽 while이 있다는 문법만으로 $O(N^{2})$라고 판단할 수 없는 이유이다.

∎

$a<b$에 대해 $q=\min (\mathrm{LCP}[a+1],\ldots ,\mathrm{LCP}[b])$, $h=\operatorname{lcp}(S[\mathrm{SA}[a]\ldots ],S[\mathrm{SA}[b]\ldots ])$라 두자.

$h\ge q$. 구간 안의 모든 인접 접미사 쌍이 앞 q글자를 공유한다. 동일성의 추이성으로 구간 양 끝도 앞 q글자를 공유한다.

$q\ge h$. 양 끝 접미사가 앞 h글자를 공유하므로 보조정리 3에 의해 사이의 모든 접미사가 그 접두사를 공유한다. 따라서 모든 인접 LCP가 h 이상이고 그 최솟값 q도 h 이상이다.

두 부등식을 합치면 $h=q$이다. 동일한 시작 위치 $i=j$이면 비교 대상이 같으므로 $\mathrm{LCP}=N-i$이며, 비어 있는 RMQ 구간을 질의하지 않는다.

∎

Sparse Table. $\operatorname{st}[k][i]$에 i에서 시작하는 길이 $2^{k}$ 구간의 최솟값을 저장한다. 길이 절반인 두 구간의 최솟값으로 계산할 수 있으므로 $O(N \log N)$ 시간·공간이다. 길이 d인 질의는 $k=\lfloor \log _{2}d\rfloor$로 두고 양 끝의 길이 $2^{k}$ 구간 두 개로 덮는다. 두 구간이 겹쳐도 $\min (x,x)=x$이므로 답이 변하지 않는다. 로그를 전처리하면 질의는 $O(1)$이다.

두 구간이 빠짐없이 덮는 이유. $q=2^{k}$라 두면 $q\le d<2q$이다. $[l,l+q)$와 $[r-q,r)$는 모두 질의 $[l,r)$ 안에 있고$, d\le 2q$이므로 사이에 빈틈이 없다. 두 구간의 합집합이 정확히 질의 구간이며 중복은 min의 멱등성으로 제거된다. 전처리 점화식도 길이 1을 기초로 길이별 귀납하면 정확하다.

Segment Tree. 각 부모를 두 자식의 최솟값으로 구성하면 $O(N)$개의 노드를 한 번씩 처리한다. 구간 질의는 각 깊이에서 양 경계에 걸친 노드만 더 내려가므로 $O(\log N)$개의 대표 구간으로 분해된다. 구성·공간은 $O(N)$, 질의는 $O(\log N)$이다.

SA-IS의 선형 시간은 이 페이지에서 구현하거나 증명하는 범위가 아니다. 정수 알파벳에 대한 별도 알고리즘이며, 위 Doubling 구현의 복잡도와 구분한다.

∎

서로 다른 부분 문자열 수. 모든 비어 있지 않은 부분 문자열은 어떤 접미사의 접두사이다. SA 순서에서 현재 접미사의 길이를 $\ell$, 이전 이웃과의 LCP를 h라 하자. 길이 1,…,h인 접두사는 이미 등장했다. 길이 h보다 긴 접두사가 더 앞선 접미사에 있었다면, 보조정리 3에 의해 바로 이전 이웃도 이를 공유해야 하므로 h의 정의에 모순이다. 따라서 새로 추가되는 부분 문자열은 정확히 $\ell -h$개이다. 합산하면 $N(N+1)/2 - \sum_{r=0}^{N-1}\mathrm{LCP}[r]$이다.

최장 반복 부분 문자열. 인접 LCP가 h이면 서로 다른 두 시작 위치에서 길이 h의 문자열이 등장한다. 역으로 길이 L의 문자열이 두 번 이상 등장하면, 그 문자열을 접두사로 갖는 접미사들은 SA의 연속 구간을 이룬다. 해당 구간에는 인접 쌍이 있고 LCP가 L 이상이다. 따라서 겹침을 허용한 최장 반복 부분 문자열 길이는 $\max_{0\le r<N}\mathrm{LCP}[r]$이다. 빈 입력은 답 0으로 처리한다.

∎

구간 비교. 두 부분 문자열의 길이가 $\ell _{1}, \ell _{2}$이고 시작 위치의 suffix LCP가 h라면 공통 부분 길이는 $\min (h,\ell _{1},\ell _{2})$이다. 이 값이 더 짧은 구간 길이이면 prefix 관계이므로 길이를 비교하고, 아니면 바로 다음 문자에서 순서가 결정된다.

패턴 검색. 패턴 P로 시작하는 접미사들은 보조정리 3에 의해 연속 구간을 이룬다. 접미사의 앞 $|P|$글자와 P의 비교 결과는 SA에서 음수·0·양수 순으로 나타나므로 lower/upper bound로 구간의 양 끝을 찾을 수 있다. 비교 한 번이 $O(|P|)$, 비교 횟수가 $O(\log N)$이므로 단순 구현은 $O(|P|\log N)$이다. 결과 위치 K개를 출력하면 $O(K)$가 추가된다.

이분 탐색의 정당성. lower bound의 조건은 비교 결과가 0 이상, upper bound의 조건은 양수이다. 각각 거짓 뒤에 참이 오는 단조 조건이다. 답을 첫 참 위치(없으면 N)로 두면, 반복 진입 시 답은 닫힌 인덱스 구간 $[l,r]$ 안에 있다. mid가 거짓이면 mid 이하를 버려 $l=mid+1$, 참이면 답이 mid보다 뒤일 수 없어 $r=mid$로 둔다. 구간 길이가 엄격히 감소해 $l=r$로 종료하고, 불변식상 그 값이 답이다. 따라서 두 반환값 사이에 정확히 일치 접미사들만 남는다.

∎

서로 다른 문자열 사이에 입력에 없는 서로 다른 구분자를 넣고 각 접미사의 원본 문자열을 기록한다. 서로 다른 원본의 두 접미사가 일치하는 구간은 서로 다른 구분자를 동시에 통과할 수 없으므로 원본 경계를 넘어 확장되지 않는다.

두 문자열. 공통 부분 문자열 P가 있으면 P를 접두사로 갖는 SA 구간에 두 원본의 접미사가 모두 있다. 이 구간 안에는 원본 소속이 바뀌는 인접 쌍이 있으며 그 LCP는 $|P|$ 이상이다. 역으로 서로 다른 원본의 접미사 쌍의 LCP는 실제 공통 부분 문자열이다. 따라서 소속이 다른 인접 쌍의 최대 LCP로 최장 공통 부분 문자열을 구할 수 있다.

세 문자열 이상. 모든 원본을 포함하는 SA 구간을 고려해야 한다. 정리 6에 의해 구간의 인접 LCP 최솟값은 구간 전체가 공유하는 접두사 길이이다. 모든 원본이 등장하는 구간 중 이 값의 최댓값을 구하면 답이 된다. 단순히 소속이 다른 인접 쌍만 확인하면 모든 원본에 공통이라는 조건을 보장하지 못한다.

∎