Suffix Array

1정의#

길이 n인 문자열 S에서 위치 i에서 시작하는 접미사를 suf(i)라 한다. Suffix Array SA는 모든 접미사를 사전순으로 정렬한 [0, n)의 순열이다. 임의의 i < j에 대해 suf(SA_i) < suf(SA_j)가 성립한다.

2구현#

접미사를 직접 비교 정렬한다. 접미사 하나 비교에 최대 O(n), 정렬에 O(n log n)번 비교하므로 O(n² log n)이다.

vector<int> suffix_array(const string& s) {
    int n = s.size();
    vector<int> sa(n);
    iota(sa.begin(), sa.end(), 0);
    sort(sa.begin(), sa.end(), [&](int a, int b) {
        return s.substr(a) < s.substr(b);
    });
    return sa;
}