Suffix Array

A suffix array lists the starting positions of all nonempty suffixes of a string in lexicographic order. For a text of length n there are n suffixes, yet storing their starting positions requires only O(n) space. This ordering is useful because suffixes beginning with the same pattern become consecutive. It turns substring matching, repeated-substring analysis, and lexicographic questions into problems about a sorted array. The difficult part is building that array without repeatedly comparing whole suffixes. We will use the standard doubling method with comparison sorting. This implementation is deliberately straightforward: its construction time is O(n log² n), rather than claiming the faster bound of radix-sorted variants.

Prerequisites: String indexing, lexicographic comparison, sorting, pairs, equivalence classes, logarithms.

Build the idea

1. 1. Suffixes, positions, and lexicographic order

   Use 0-based string indices. For banana, positions 0 through 5 identify banana, anana, nana, ana, na, a. Sorting them gives a, ana, anana, banana, na, nana, so SA=[5,3,1,0,4,2]. SA[r] is the start of the suffix with sorted rank r; it is not its length. When one suffix is a prefix of another, the shorter comes first: a precedes ana. We exclude the empty suffix at position n. There is no extra sentinel character in this program, so the output always contains exactly n positions.

2. 2. Replace long comparisons with ranks

   Initially rank[i] describes the first character of the suffix at i. Suppose ranks describe prefixes of length width. A prefix of length 2*width consists of two consecutive blocks: its current rank and the rank at i+width. Sorting suffixes by the pair (rank[i],rank[i+width]) therefore sorts their doubled prefixes. If the second block is absent, use rank -1, smaller than any real rank. This models the rule that an exhausted string sorts before a longer string sharing its prefix. The pair contains integers, so each comparison takes constant time.

3. 3. Turn sorted pairs into equivalence classes

   After sorting, assign class 0 to the first suffix. Move through the sorted array; increase the class only when the current pair differs from the previous pair. Equal pairs must get equal ranks because they describe equal prefixes. Unequal ranks preserve lexicographic order. Store these new ranks in a separate array; overwriting old ranks during sorting or class assignment would change pair meanings halfway through the round. Swapping the two arrays completes the round and reestablishes the invariant for the doubled prefix length.

4. 4. A concrete doubling trace

   In banana, width 1 compares ba, an, na, an, na, a. The a at position 5 gets the first class, positions 1 and 3 share the next class, position 0 follows, and positions 2 and 4 share the last class. Thus the resulting ranks by original position are [2,1,3,1,3,0]. With width 2, position 3 has pair (1,0), while position 1 has (1,1), so ana sorts before anana. Position 4 has (3,-1), while position 2 has (3,3), so na sorts before nana. Every suffix is now distinguished and the process stops.

5. 5. Why the algorithm is correct

   The base ranks compare one-character prefixes correctly. If length-width ranks compare their prefixes correctly, comparing first-block ranks and breaking ties with second-block ranks exactly matches lexicographic comparison of doubled prefixes. This is an induction on the doubling rounds. Once a compared prefix covers the whole remaining suffix, no unseen character can reverse its order. An earlier stop is also safe when every suffix has a distinct class: each pair already identifies its unique position in sorted order, so later characters cannot alter a comparison already decided by an earlier difference.

6. 6. Use the result without copying suffix strings

   To search for pattern P, binary-search the sorted suffixes while comparing P directly against text characters starting at SA[mid]. A simple implementation spends O(|P|) per comparison and therefore O(|P| log n) per search; merely possessing a suffix array does not make each string comparison constant-time. Adjacent suffixes and their longest common prefixes lead to repeated-substring counting in the next lesson. Keep SA as positions rather than materializing s.substr(i) for every suffix, which would consume quadratic total characters.

7. 7. Read and test the program

   The program uses getline, so spaces are part of the text and an empty line is a valid empty text. Character ranks use unsigned byte values for consistent ordering. n=0 returns an empty array; n=1 needs no doubling round. The explicit input bound keeps index arithmetic and doubling safely inside int. Try banana, all-equal aaaa, and a string with all different characters. In aaaa, the shortest suffix must come first, demonstrating why the missing-block rank is essential even when no two characters differ.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>
#include<utility>
using namespace std;
vector<int>suffixArray(const string&s){
    int n=(int)s.size();
    vector<int>sa(n),rank(n),nextRank(n);
    iota(sa.begin(),sa.end(),0);
    // Initial ranks encode one-byte prefixes, not signed char values.
    for(int i=0;i<n;i++){
        rank[i]=(unsigned char)s[i];
    }
    for(int width=1;width<n;width*=2){
        // Missing second halves sort before every real suffix rank.
        auto key=[&](int i){
            return make_pair(rank[i],i+width<n?rank[i+width]:-1);
        };
        sort(sa.begin(),sa.end(),[&](int a,int b){
            return key(a)<key(b);
        });
        // Equal pairs must receive the same new class.
        nextRank[sa[0]]=0;
        for(int j=1;j<n;j++){
            nextRank[sa[j]]=nextRank[sa[j-1]]+(key(sa[j-1])!=key(sa[j]));
        }
        rank.swap(nextRank);
        if(rank[sa.back()]==n-1){
            break; // Every suffix is distinguished.
        }
    }
    return sa;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin,s);
    vector<int>sa=suffixArray(s);
    // Print positions only; never allocate copies of all suffix strings.
    for(int i=0;i<(int)sa.size();i++){
        if(i){
            cout<<' ';
        }
        cout<<sa[i];
    }
    cout<<'\n';
}

Complexity analysis

Each round comparison-sorts n constant-size rank pairs in O(n log n); at most O(log n) rounds give O(n log² n) construction. Arrays and sort stack use O(n) total auxiliary storage. Output takes O(n). Radix/counting sorting the classes can improve construction to O(n log n), but is not implemented here.

Example input and output

One entire line of text, possibly empty or containing spaces. Length 0≤n≤200000; input is treated as bytes. Output one line of 0-based starts of all n nonempty suffixes in ascending lexicographic order; an empty text produces a blank line.

Input

banana

Output

5 3 1 0 4 2

The sorted suffixes are a, ana, anana, banana, na, nana. Their starting positions are 5,3,1,0,4,2.

Practical applications

Static substring search; lexicographic substring questions; longest repeated substrings with LCP; counting distinct substrings; indexing texts. A suffix automaton offers a different, online representation of substring information.

Check your understanding

Why is the rank of an absent second block -1?

Put it into practice

Use the suffix array to check whether a query pattern occurs in the text.