Introduction

A suffix array stores the starting positions of all suffixes of a string in lexicographic order. The classic way to build one in O(n log n) time is the doubling algorithm: repeatedly sort suffixes by the first 2^k characters while reusing the ranks computed in the previous pass.

The Core Idea Behind the Doubling Method

Suppose the input string is banana. At the start, each suffix can be ranked by just its first character. After that, you sort suffixes by pairs of ranks:

• current rank of position i
• current rank of position i + 2^k

Once those pairs are sorted, you assign new ranks and double the compared prefix length for the next round.

The important observation is that if you already know the order of prefixes of length 2^k, then the order of prefixes of length 2^(k+1) can be derived from rank pairs instead of by comparing long strings character by character.

A Runnable O(n log n) Implementation in C++

To keep the overall complexity at O(n log n), each round must sort rank pairs in linear time, usually with counting sort because the ranks are integers in the range 0 through n - 1.

1#include <algorithm>
2#include <iostream>
3#include <string>
4#include <vector>
5using namespace std;
6
7vector<int> build_suffix_array(const string& s) {
8    string text = s + "$";
9    int n = static_cast<int>(text.size());
10    vector<int> sa(n), rank(n);
11
12    {
13        vector<pair<char, int>> a(n);
14        for (int i = 0; i < n; ++i) {
15            a[i] = {text[i], i};
16        }
17        sort(a.begin(), a.end());
18        for (int i = 0; i < n; ++i) {
19            sa[i] = a[i].second;
20        }
21        rank[sa[0]] = 0;
22        for (int i = 1; i < n; ++i) {
23            rank[sa[i]] = rank[sa[i - 1]] + (a[i].first != a[i - 1].first);
24        }
25    }
26
27    for (int k = 0; (1 << k) < n; ++k) {
28        int len = 1 << k;
29        for (int i = 0; i < n; ++i) {
30            sa[i] = (sa[i] - len + n) % n;
31        }
32
33        vector<int> count(n), new_sa(n);
34        for (int x : rank) {
35            count[x]++;
36        }
37        for (int i = 1; i < n; ++i) {
38            count[i] += count[i - 1];
39        }
40        for (int i = n - 1; i >= 0; --i) {
41            int start = sa[i];
42            int cls = rank[start];
43            new_sa[--count[cls]] = start;
44        }
45        sa = new_sa;
46
47        vector<int> new_rank(n);
48        new_rank[sa[0]] = 0;
49        for (int i = 1; i < n; ++i) {
50            pair<int, int> prev = {rank[sa[i - 1]], rank[(sa[i - 1] + len) % n]};
51            pair<int, int> curr = {rank[sa[i]], rank[(sa[i] + len) % n]};
52            new_rank[sa[i]] = new_rank[sa[i - 1]] + (curr != prev);
53        }
54        rank = new_rank;
55    }
56
57    sa.erase(sa.begin());
58    return sa;
59}
60
61int main() {
62    string s = "banana";
63    vector<int> sa = build_suffix_array(s);
64    for (int index : sa) {
65        cout << index << ' ';
66    }
67    cout << '\n';
68}

For banana, the output is 5 3 1 0 4 2, which is the expected suffix array.

Why the Complexity Is O(n log n)

There are about log n rounds because the compared prefix length doubles each time. If each round uses counting sort on integer ranks, the work per round is linear in n.

That gives the total complexity:

• 'O(n) work per doubling round'
• 'O(log n) rounds'
• total O(n log n)

If you replace counting sort with a comparison sort in every round, the complexity becomes O(n log^2 n). The doubling idea is still the same, but the asymptotic guarantee changes.

Reading the Data Structures

The main arrays in the algorithm each have a specific job:

• 'sa stores the current order of suffix starts'
• 'rank stores the equivalence class of each suffix prefix'
• 'count supports counting sort over rank values'

Once all suffixes have distinct ranks, the ordering is complete. The sentinel character "$" ensures every suffix is properly terminated and that one suffix is strictly smallest.

This representation is also useful beyond construction. A suffix array can support substring search with binary search, and it is the starting point for building the LCP array used in many string algorithms.

Common Pitfalls

A common mistake is calling a tuple-based comparison sort in each doubling round and then claiming the implementation is O(n log n). Without radix or counting sort on integer ranks, it is usually O(n log^2 n).

Another mistake is forgetting the sentinel character. Without a unique smallest terminator, cyclic shifts and true suffixes become harder to separate correctly.

Indexing bugs are also common when computing the second half of a rank pair. In cyclic-shift style implementations, the second index is wrapped with modulo arithmetic until the sentinel is removed at the end.

Finally, be clear about the difference between algorithm idea and language implementation. The doubling method supports O(n log n), but only if the per-round sorting step respects that bound.

Summary

• A suffix array stores suffix starting indices in lexicographic order.
• The doubling method sorts suffixes by rank pairs for prefixes of length 2^k.
• Counting sort on integer ranks keeps each round linear.
• Using comparison sort each round changes the bound to O(n log^2 n).
• The sentinel character and careful rank updates are essential for correctness.