# O(N) Suffix Array

**Người viết:**
> **Nguyễn Tường Duy - VNU University of Engineering and Technology**

## Bài toán

Cho xâu $S$ độ dài $n$ thỏa mãn $S[i] \leq n$ ($1 \leq i \leq n$), sắp xếp các hậu tố của $S$ theo thứ tự từ điển (hậu tố của $S$ được biểu diễn bằng vị trí $i$ tương ứng với $S[i, n]$), gọi mảng đã sắp xếp đó là mảng hậu tố.

## Skew Algorithm

Ý tưởng của thuật toán là:

**Bước 1.** Sắp xếp các hậu tố ở vị trí $i$ mod $3 \neq 0$.
**Bước 2.** Sắp xếp các hậu tố ở vị trí $i$ mod $3 = 0$ sử dụng kết quả của bước 1.
**Bước 3.** Gộp mảng hậu tố ở bước $1$ và $2$ bằng thuật toán merge sort.

### Bước 1

Đầu tiên ta sắp xếp các hậu tố ở vị trí $i$ mod $3 \neq 0$ theo giá trị của hậu tố $i$ là $S[i, i + 2]$. Ta sẽ dùng thuật toán counting sort để sắp xếp trong thời gian $O(n)$.

Nếu các giá trị của hậu tố phân biệt thì ta đã hoàn thành bước $1$. Nếu không thì ta sẽ sắp xếp các hậu tố này theo cách đệ quy.

Cụ thể hơn ta có mảng $S_{12} = [1, 4, 7, \dots, 2, 5, 8, \dots]$, ta sẽ sắp xếp $S_{12}$ theo các giá trị sau: $[S[1, 3], S[4, 6], S[7, 9], \dots, -\infty, S[2, 4], S[5, 7], S[8, 10], \dots]$ (thêm giá trị $-\infty$ vào giữa để ngăn cách hậu tố $i$ mod $3 = 1$ với $i$ mod $3 = 2$).
Sau khi sắp xếp xong ta sẽ có mảng $e$ là giá trị tương đương của các hậu tố ($e$ thỏa mãn hậu tố $i <$ hậu tố $j$ thì $e[i] < e[j]$, hậu tố $i =$ hậu tố $j$ thì $e[i] = e[j]$). Ta sẽ tính đệ quy mảng hậu tố của mảng $[e[S_{12}[1]], e[S_{12}[2]], \dots]$. Ta thấy hậu tố của mảng $e$ tương đương với các hậu tố trong mảng $S_{12}$.
(ví dụ hậu tố $1$ là $[S[1], S[2], S[3], S[4], S[5], S[6], \dots] = [e[S[1, 3]], e[S[4, 6]], \dots]$)

### Bước 2

Ta sẽ sắp xếp các hậu tố ở vị trí $i$ mod $3 = 0$ theo giá trị của hậu tố $i$ là $S[i]$ và thứ tự của hậu tố $i + 1$ trong mảng hậu tố ở bước $1$. Ta dùng thuật toán counting sort để sắp xếp trong thời gian $O(n)$.

### Bước 3

Để gộp hai mảng hậu tố bằng thuật toán merge sort thì ta cần so sánh hậu tố $i$ mod $3 = 0$ với hậu tố $j$ mod $3 \neq 0$. Ta sẽ so sánh hai hậu tố trong thời gian $O(1)$ như sau:

* So sánh hậu tố $i$ mod $3 = 0$ và $j$ mod $3 = 1$ bằng cách so sánh $S[i]$ và $S[j]$, vị trí của hậu tố $i + 1$ và hậu tố $j + 1$ trong mảng hậu tố ở bước $1$.
* So sánh hậu tố $i$ mod $3 = 0$ và $j$ mod $3 = 2$ bằng cách so sánh $S[i]$ và $S[j]$, so sánh $S[i + 1]$ và $S[j + 1]$, vị trí của hậu tố $i + 2$ và hậu tố $j + 2$ trong mảng hậu tố ở bước $1$.

## Tổng kết

Ta sẽ phân tích độ phức tạp thời gian ở từng bước:
* **Bước 1:** $O(n + \frac{2}{3} \cdot n + \frac{4}{9} \cdot n + \dots) = O(n)$
* **Bước 2:** $O(n)$
* **Bước 3:** $O(n)$

Như vậy ta được thuật toán có độ phức tạp thời gian $O(n)$.

## Cài đặt

Những lưu ý khi code:

* $n = 1$ thì mảng hậu tố là $[0]$.
* Ta sẽ thêm $2$ phần tử $0$ vào cuối xâu $S$ để code dễ hơn.
* Khi sắp xếp đệ quy mảng hậu tố ở bước $1$ thì ta sẽ thêm giá trị tương ứng với $-\infty$ giữa hậu tố $i$ mod $3 = 1$ với $i$ mod $3 = 2$.

Code:

void counting_sort(vector<int> &arr, const vector<int>::iterator &val) {
    int ma = 0;
    for (int &x: arr) ma = max(ma, val[x]);
    vector<int> cnt(ma + 1);
    for (int &x: arr) ++cnt[val[x]];
    for (int i = 0, sum = 0; i <= ma; ++i) {
        int tmp = cnt[i];
        cnt[i] = sum;
        sum += tmp;
    }
    vector<int> new_arr(arr.size());
    for (int &x: arr) new_arr[cnt[val[x]]++] = x;
    arr = new_arr;
}
vector<int> suffix_array(vector<int> s) {
    int n = s.size();
    if (n == 1) return vector<int>(1);
    s.resize(n + 2);
    int n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3, n12 = n1 + n2;
    vector<int> sa12(n12);
    for (int i = 0; i < n1; ++i) sa12[i] = i * 3 + 1;
    for (int i = 0; i < n2; ++i) sa12[i + n1] = i * 3 + 2;
    counting_sort(sa12, s.begin() + 2);
    counting_sort(sa12, s.begin() + 1);
    counting_sort(sa12, s.begin());
    vector<int> equiv(n + 1);
    equiv[sa12[0]] = 2;
    for (int i = 1; i < n12; ++i) equiv[sa12[i]] = equiv[sa12[i - 1]] + (s[sa12[i]] != s[sa12[i - 1]] ||
                                                                         s[sa12[i] + 1] != s[sa12[i - 1] + 1] ||
                                                                         s[sa12[i] + 2] != s[sa12[i - 1] + 2]);
    if (equiv[sa12[n12 - 1]] <= n12) {
        vector<int> s12(n12 + 1);
        for (int i = 0; i < n1; ++i) s12[i] = equiv[i * 3 + 1];
        s12[n1] = 1;
        for (int i = 0; i < n2; ++i) s12[i + n1 + 1] = equiv[i * 3 + 2];
        sa12 = suffix_array(s12);
        sa12.erase(sa12.begin());
        for (int &x: sa12) x = x < n1 ? x * 3 + 1 : (x - n1) * 3 - 1;
        equiv[sa12[0]] = 2;
        for (int i = 1; i < n12; ++i) equiv[sa12[i]] = equiv[sa12[i - 1]] + 1;
    }
    vector<int> sa0(n0);
    for (int i = 0; i < n0; ++i) sa0[i] = i * 3;
    counting_sort(sa0, equiv.begin() + 1);
    counting_sort(sa0, s.begin());
    vector<int> sa(n);
    int i = 0, j = 0, k = 0;
    while (i < n12 && j < n0) {
        int suff12 = sa12[i], suff0 = sa0[j];
        while (true) {
            if (s[suff12] != s[suff0]) {
                sa[k++] = s[suff12] < s[suff0] ? sa12[i++] : sa0[j++];
                break;
            }
            ++suff12, ++suff0;
            if (equiv[suff12] && equiv[suff0]) {
                sa[k++] = equiv[suff12] < equiv[suff0] ? sa12[i++] : sa0[j++];
                break;
            }
        }
    }
    while (i < n12) sa[k++] = sa12[i++];
    while (j < n0) sa[k++] = sa0[j++];
    return sa;
}

## Tham khảo

https://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf