접미사 배열과 LCP

O(N log N) 접미사 정렬과 카사이 알고리즘.

플래티넘 II

1강 접미사 정렬과 LCP 배열 공식

접미사 배열이란

문자열 $$S$$ (길이 $$N$$ )의 모든 접미사를 사전순으로 정렬했을 때, 각 접미사의
시작 인덱스를 정렬 순서대로 나열한 배열이 접미사 배열(suffix array, SA) 이다.
$\texttt{banana}$ 라면 접미사 6개를 사전순 정렬해 그 시작 위치를 적는다.

접미사 배열은 "패턴 검색", "서로 다른 부분 문자열 개수", "최장 반복 부분 문자열"
등 문자열 문제 전반의 만능 도구다. 패턴 $$P$$ 의 등장 여부는 SA 위에서 이분
탐색으로 $O(|P| \log N)$ 에 판정한다.

$O(N \log^2 N)$ 정렬: 배수 증가법

접미사 전체를 직접 비교하면 한 비교가 $$O(N)$$ 이라 너무 느리다. 대신 길이
$$2^k$$ 접두사 기준 순위(rank) 를 $$k$$ 를 두 배씩 늘려 가며 계산한다.

$$k=0$$ : 각 위치의 한 글자로 순위를 매긴다.
$k \to k+1$ : 위치 $$i$$ 의 길이 $2^{k+1}$ 접두사 순위는, (현재 순위, $$i+2^k$$
위치의 현재 순위) 쌍으로 정한다. 이미 길이 $$2^k$$ 순위를 알므로 쌍 비교가
$$O(1)$$ 이다.

각 단계 정렬이 $O(N \log N)$ 이고 단계가 $O(\log N)$ 이라 $O(N \log^2 N)$ .
정렬을 기수 정렬로 바꾸면 $O(N \log N)$ 이 된다.

LCP 배열

LCP(Longest Common Prefix) 배열은 접미사 배열에서 이웃한 두 접미사의
최장 공통 접두사 길이를 담는다. $\text{lcp}[i]$ 는 SA에서 $$i$$ 번째와 $$i-1$$ 번째
접미사의 공통 접두사 길이다.

LCP가 있으면 강력한 사실들이 따라온다.

서로 다른 부분 문자열 개수 $= \dfrac{N(N+1)}{2} - \sum_i \text{lcp}[i]$ .
SA에서 연속 구간의 최솟값 LCP = 그 구간 접미사들의 공통 접두사 길이.

카사이 알고리즘

LCP 배열을 $$O(N)$$ 에 구하는 방법이다. 원문에서 위치 순서대로 보면서, 한 접미사의
LCP를 구한 뒤 다음(한 글자 짧은) 접미사로 넘어갈 때 공통 접두사 길이가 최대
1만 줄어든다는 성질을 이용한다. 그래서 전체 비교 횟수가 분할상환 $$O(N)$$ 이다.

$\text{lcp}[\text{rank}[i]] \ge \text{lcp}[\text{rank}[i-1]] - 1$

이 한 줄의 단조성이 카사이가 선형인 핵심이다.

2강 구현과 활용 공식

SA + LCP 구현 ( $O(N \log^2 N)$ + 카사이)

sa[i] = 정렬 $$i$$ 번째 접미사 시작 위치, rk[p] = 위치 $$p$$ 접미사의 순위.

#include <bits/stdc++.h>
using namespace std;

vector<int> suffix_array(const string& s) {
    int n = s.size(), k;
    vector<int> sa(n), rk(n), tmp(n);
    for (int i = 0; i < n; i++) { sa[i] = i; rk[i] = s[i]; }
    for (k = 1; ; k <<= 1) {
        auto cmp = [&](int a, int b) {
            if (rk[a] != rk[b]) return rk[a] < rk[b];
            int ra = a + k < n ? rk[a + k] : -1;
            int rb = b + k < n ? rk[b + k] : -1;
            return ra < rb;             // 뒤 절반 순위 비교
        };
        sort(sa.begin(), sa.end(), cmp);
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++)
            tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
        rk = tmp;
        if (rk[sa[n - 1]] == n - 1) break;   // 모든 순위가 distinct면 종료
    }
    return sa;
}

vector<int> kasai(const string& s, const vector<int>& sa) {
    int n = s.size();
    vector<int> rk(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rk[sa[i]] = i;
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rk[i] == 0) { h = 0; continue; }
        int j = sa[rk[i] - 1];               // SA 상 앞 접미사
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
        lcp[rk[i]] = h;
        if (h) h--;                          // 다음 위치로 갈 때 최대 1 감소
    }
    return lcp;
}

흔한 실수

종료 조건 — 모든 순위가 서로 다르면(rk[sa[n-1]] == n-1) 더 정렬할 필요가
없다. 이 조기 종료가 없으면 불필요한 단계가 돈다.
경계 인덱스 — $a + k \ge n$ 이면 그쪽 순위를 $$-1$$ (가장 작음)로 둬야 짧은
접미사가 앞에 온다.
카사이의 h-- — 다음 위치로 넘어갈 때 $$h$$ 를 1 줄이는 것이 선형성의
핵심이다. 이를 빼면 $$O(N^2)$$ 가 된다.
rank/sa 혼동 — sa는 순위→위치, rk는 위치→순위. 둘을 헷갈리면 전부
틀린다.

활용

문제	풀이
서로 다른 부분 문자열 수	$N(N+1)/2 - \sum \text{lcp}$
최장 반복 부분 문자열	LCP 배열의 최댓값
패턴 검색	SA 위 이분 탐색 $O(\|P\|\log N)$
두 접미사의 LCP	LCP 배열 구간 최솟값(스파스 테이블)

더 빠른 $$O(N)$$ 접미사 배열(DC3/SA-IS)도 있지만, 위 $O(N \log^2 N)$ 구현이
대부분의 대회 범위에서 충분히 빠르고 외우기 쉽다. 접미사 배열은 이후 등장하는
접미사 오토마톤과 더불어 문자열 자료 구조의 핵심 축이다.