Suffix Arrays: Manber-Myers O(N log N) Prefix Doubling & SA-IS O(N) Overview

1. Manber-Myers $O(N \log N)$ Prefix Doubling

Append a sentinel $\texttt{'\$'}$ (smaller than any alphabet character) to $S$ so its length is $N$, and sort all cyclic shifts of $S$ (which is identical to sorting all suffixes because $\texttt{'\$'}$ breaks ties before wrapping around). At iteration $k = 0, 1, \dots, \lceil \log_2 N \rceil$:

• Maintain the array $\text{sa}[0..N-1]$ of starting indices sorted by their $2^k$-length prefixes, and the equivalence class array $c[i] \in [0, N-1]$ giving the lexicographical rank of $S[i .. i + 2^k - 1]$.
• To transition from length $2^k$ to $2^{k+1}$, each position $i$ is represented by the 2-tuple of ranks $(c[i],\; c[(i + 2^k) \bmod N])$.
• Single-Pass Counting Sort Trick: We do NOT need two counting sorts per step! Because $\text{sa}[0..N-1]$ is already sorted by the second component if we shift each index backward by $2^k$ ($\text{sa}'[j] = (\text{sa}[j] - 2^k + N) \bmod N$), we only need one stable counting sort on the first component $c[\text{sa}'[j]]$!
• Early Exit Optimization: As soon as the number of distinct equivalence classes reaches $N$, all suffixes are strictly ordered and we terminate immediately without running remaining doubling steps.

2. SA-IS ($O(N)$ Suffix Array via Induced Sorting)

How does SA-IS (Nong, Zhang, Chan 2009) eliminate the $\log N$ factor? It classifies every suffix $i$ into one of two types in a single right-to-left scan:

• S-type (Smaller): Suffix $S[i..]$ is lexicographically strictly smaller than the next suffix $S[i+1..]$, i.e., $S[i] < S[i+1]$ or ($S[i] == S[i+1]$ and $i+1$ is S-type). The sentinel $S[N-1] = \texttt{'\$'}$ is S-type by definition.
• L-type (Larger): Suffix $S[i..]$ is strictly larger than $S[i+1..]$.
• LMS (Leftmost S-type) Positions: An index $i > 0$ is an LMS position if $i$ is S-type and $i - 1$ is L-type. Notice that two adjacent indices can never both be LMS, so there are at most $N / 2$ LMS positions!

SA-IS sorts only the LMS substrings (recursively if LMS substrings have ties, on a string of length $\le N / 2$), places the sorted LMS suffixes at the ends of their character buckets, and then induces the sorted order of all L-type suffixes in one left-to-right pass (scanning $\text{SA}$ left-to-right: if $\text{SA}[j] - 1$ is L-type, place it at the front of bucket $S[\text{SA}[j] - 1]$) followed by all S-type suffixes in one right-to-left pass! By the recurrence $T(N) = T(N/2) + O(N) = O(N)$, SA-IS runs in linear time.

3. Visual Trace: Suffix Array & L/S/LMS Classification on $S = \texttt{"banana\$"}$

4. Production Implementation: $O(N \log N)$ Prefix Doubling + Pattern Binary Search

#include <algorithm>
#include <cstdint>
#include <string>
#include <string_view>
#include <utility>
#include <vector>

// Builds Suffix Array in O(N log N) time using Manber-Myers Prefix Doubling
std::vector<int> build_suffix_array(std::string_view str) {
    // Append '' sentinel (strictly smaller than any printable char)
    const int n = static_cast<int>(str.size()) + 1;
    const int alpha = 256;
    std::vector<int> p(n), c(n), cnt(std::max(alpha, n), 0);

    for (int i = 0; i < n - 1; ++i) cnt[static_cast<uint8_t>(str[i])]++;
    cnt[0]++; // Sentinel at n - 1
    for (int i = 1; i < alpha; ++i) cnt[i] += cnt[i - 1];
    for (int i = 0; i < n; ++i) {
        uint8_t ch = (i == n - 1) ? 0 : static_cast<uint8_t>(str[i]);
        p[--cnt[ch]] = i;
    }

    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; ++i) {
        uint8_t ch_cur = (p[i] == n - 1) ? 0 : static_cast<uint8_t>(str[p[i]]);
        uint8_t ch_prv = (p[i - 1] == n - 1) ? 0 : static_cast<uint8_t>(str[p[i - 1]]);
        if (ch_cur != ch_prv) ++classes;
        c[p[i]] = classes - 1;
    }

    std::vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n && classes < n; ++h) {
        int step = 1 << h;
        for (int i = 0; i < n; ++i) {
            pn[i] = p[i] - step;
            if (pn[i] < 0) pn[i] += n;
        }
        std::fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; ++i) cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; ++i) cnt[i] += cnt[i - 1];
        for (int i = n - 1; i >= 0; --i) p[--cnt[c[pn[i]]]] = pn[i];

        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; ++i) {
            std::pair<int, int> cur = {c[p[i]], c[(p[i] + step) % n]};
            std::pair<int, int> prv = {c[p[i - 1]], c[(p[i - 1] + step) % n]};
            if (cur != prv) ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }

    p.erase(p.begin()); // Remove the '' sentinel suffix at p[0] == n - 1
    return p;
}

// Returns half-open range [L, R) in SA where pattern P occurs as a prefix
std::pair<int, int> suffix_array_search(std::string_view text,
                                        const std::vector<int>& sa,
                                        std::string_view pat) {
    auto cmp_lower = [&](int idx, std::string_view q) {
        return text.substr(idx, q.size()) < q;
    };
    auto cmp_upper = [&](std::string_view q, int idx) {
        return q < text.substr(idx, q.size());
    };
    auto l = std::lower_bound(sa.begin(), sa.end(), pat, cmp_lower);
    auto r = std::upper_bound(l, sa.end(), pat, cmp_upper);
    return {static_cast<int>(l - sa.begin()), static_cast<int>(r - sa.begin())};
}