On this page

Suffix Arrays & LCP

Why this exists

Every lesson so far in this module has had the same shape: you get a pattern and a text, you preprocess the pattern, and you scan the text once. KMP builds a table from the pattern. Aho–Corasick builds an automaton from a set of patterns. Each scan costs , where is the length of the text.

Now flip the situation. The text is huge and it does not change: a human genome (about 3.1 billion letters), the source code of a large company, a training corpus for a language model. The patterns arrive later, one at a time, and there are millions of them. Scanning 3 billion letters per query is hopeless. You want to preprocess the text once so that each query costs roughly the length of the query, not the length of the text.

The trick is an observation so simple it feels like cheating:

Every substring of is a prefix of some suffix of .

The substring nan of banana is the start of the suffix nana. The substring ban is the start of banana itself. So if you put all the suffixes in sorted (dictionary) order, every substring query becomes a search in a sorted list, and sorted lists are what binary search was made for. All suffixes that start with an sit next to each other in the sorted list, because sorting groups strings by their beginnings.

You cannot store all the suffixes as strings: their total length is , about characters for a genome. But you do not need to. A suffix is fully described by the position where it starts. So you store just the starting positions, in sorted order of the suffixes. That list of integers is the suffix array.

Udi Manber and Gene Myers introduced it in 1990 (journal version: "Suffix arrays: a new method for on-line string searches", SIAM Journal on Computing 22(5), 1993) as a space-saving alternative to the suffix tree (next-but-one lesson: Suffix Trees). A suffix tree uses around 10–20 bytes per input character in good implementations; a suffix array uses 4 bytes per character with 32-bit integers. Gaston Gonnet and colleagues developed the same structure independently for the Oxford English Dictionary project, under the name PAT array.

This lesson builds the suffix array three ways (naive sorting, prefix doubling, prefix doubling with radix sort), adds its indispensable companion, the LCP array (longest common prefix of neighbours), computed in linear time by Kasai's algorithm, and then uses the pair to answer a long list of questions that would otherwise need clever hashing or a suffix tree.

Pattern triggers

If the problem says or has…Think of…
A fixed text and many pattern queries, "does P occur", "how many times"Suffix array + binary search, per query
"number of distinct substrings"
"longest substring that appears at least twice" (overlaps allowed) of the LCP array
"longest substring that appears at least times"Max over windows of consecutive LCP values of their minimum (sliding window minimum)
"longest common substring of two strings"Suffix array of A + '#' + B, max LCP between neighbours from different strings
"-th lexicographically smallest substring" (distinct, or with repeats)Walk the suffix array, each suffix contributes new substrings
"longest common prefix of the suffixes starting at and ", many timesLCP array + sparse table range minimum, per query
"compare two substrings lexicographically", many timesRanks from the doubling rounds, or LCP + RMQ
"sum over all distinct substrings of (occurrences)²" or similarLCP array + a monotonic stack over LCP values
Huge text (genome), memory is tightSuffix array, or its compressed cousin the FM-index
"smallest rotation" or "sort all rotations"Suffix array of s + s (or the BWT view)

The meta-trigger: the question is about substrings of one fixed text, and the naive answer would enumerate substrings. Sorting the suffixes turns "all substrings" into " suffixes, plus how much neighbours share".

Intuition & first principles

Vocabulary

  • A suffix of is a piece taken from some position to the end. We name a suffix by its start index: suffix is . For banana (), suffix 0 is banana and suffix 5 is a.
  • Lexicographic order is dictionary order: compare letter by letter; the first difference decides; if one string runs out first, the shorter one is smaller (an < ana).
  • The suffix array lists suffix start positions in lexicographic order of the suffixes: is the smallest suffix, the largest.
  • The rank array is its inverse: is where suffix sits in sorted order. .
  • The LCP array (longest common prefix) stores, for each position of the sorted list, how many letters suffix shares at its start with the suffix just before it, . We set (nothing before it).

The worked example: banana

Write out all six suffixes, then sort them.

start suffix sorted position suffix
0banana05a0 (none before)
1anana13ana1 (a)
2nana21anana3 (ana)
3ana30banana0
4na44na0
5a52nana2 (na)

So:

Check the rank array: suffix 0 (banana) is at sorted position 3, so ; suffix 5 (a) is at position 0. All three arrays were produced by the code in this lesson and match a brute-force sort of the suffixes (the same example appears in the module overview).

Three things to notice already:

  1. Every substring is a prefix of a suffix, and equal prefixes are neighbours. The suffixes starting with an are rows 1 and 2, adjacent. That is why counting occurrences of an is a binary search for a block.
  2. The largest LCP is the longest repeated substring. , at row 2: ana appears twice (at positions 1 and 3, overlapping).
  3. The LCP array counts duplicates. banana has substring occurrences (pick a start and an end). Each LCP value counts prefixes that a suffix shares with the one before, which are substrings already seen. distinct substrings. We prove this later.
flowchart LR
    S["banana: 6 suffixes"] --> SORT["Sort the suffixes"]
    SORT --> SA["sa = 5 3 1 0 4 2"]
    SA --> RK["rank = inverse of sa"]
    SA --> LCP["lcp via Kasai = 0 1 3 0 0 2"]
    LCP --> Q1["max lcp = longest repeat"]
    LCP --> Q2["21 - sum lcp = distinct substrings"]
    SA --> Q3["binary search = pattern queries"]

Why sorting by "first letters" is enough to start

How do you sort suffixes faster than comparing whole strings? The key idea of prefix doubling (also called the Manber–Myers or Karp–Miller–Rosenberg doubling technique) is:

If you already know how the first letters of every suffix compare, then you can compare the first letters of any two suffixes with two numbers, without looking at a single letter.

Why: the first letters of suffix are (first letters of suffix ) followed by (first letters of suffix ). Both halves are things you have already ranked. So each suffix gets a pair of small integers, , and comparing pairs is comparing -letter prefixes. Sort the pairs, re-number them, and you know the order by letters. Start with (single letters), double to 2, 4, 8, … and after rounds , which means you are comparing whole suffixes.

Think of it as sorting people by full name when you only have a machine that sorts by one number: first number everyone by first initial; then by (first-initial number, number of the person whose name starts one letter later)… except with suffixes that "person one letter later" is just another suffix of the same string, which is what makes the trick work.

Mechanics

Rung 1: sort the suffixes directly

NAIVE-SA(s):
    return positions 0..n-1 sorted by comparing s[i:] with s[j:]

A comparison sort makes comparisons. Each comparison of two suffixes can cost up to letters (think aaaa…a, where every pair of suffixes agrees until the shorter one ends). Total: worst case. On random text, two suffixes usually differ in the first few letters, so it is close to in practice, which is why the naive version often survives in interviews. Measured in C++ (Apple M5, std::sort with string::compare, which uses a fast memcmp): all-a text of length 100,000 takes about 300 ms; length 200,000 takes about 1,250 ms. The fourfold jump for twice the input is the quadratic term showing.

Rung 2: prefix doubling with a comparison sort,

DOUBLING-SA(s):
    rank[i] = code of s[i]                   # order by the first 1 letter
    k = 1
    while some ranks are equal:
        key(i) = (rank[i], rank[i + k] if i + k < n else -1)
        sa = positions sorted by key         # comparison sort: O(n log n)
        new rank: walk sa, add 1 whenever the key changes
        k = 2k
    return sa

The -1 handles suffixes shorter than : if suffix has nothing left after its first letters (), its second half is the empty string, which is smaller than anything, so it gets the smallest possible second key. Each round is one sort of pairs, ; there are at most rounds; total . Comparing two pairs is , so the expensive letter-by-letter comparisons are gone.

The doubling trace on banana

Round 0 ranks by the first letter: a = 0, b = 1, n = 2.

012345
banana
(first 1 letter)102020
pair (1,0)(0,2)(2,0)(0,2)(2,0)(0,−1)
describesbaannaannaa
(first 2 letters)213130
pair (2,3)(1,1)(3,3)(1,0)(3,−1)(0,−1)
describesbanaanannanaananaa
(first 4 letters)325140

After round 1 (sorting by 2 letters) the order is : a, then the two an… suffixes (tied), then ba, then the two na… suffixes (tied). The ties are exactly the suffixes whose first two letters agree: suffixes 1 and 3 both start an, suffixes 2 and 4 both start na.

Round 2 breaks the ties with the pair trick. Suffix 1 gets and suffix 3 gets . Since , suffix 3 (ana) comes before suffix 1 (anan…). No letter was compared: already "knew" that a is smaller than an. After round 2 all six ranks are different, so the loop stops with

Two rounds, not : the loop stops as soon as all ranks are distinct, which here happens once , because no two suffixes of banana share their first 4 letters. The table was printed by the trace generator scripts/traces/suffix_array_doubling.py; the visualizer below plays the same run, followed by Kasai's LCP pass (explained further down).

In the visualizer the shaded window is the -letter prefix that the pair (rank[i], rank[i+k]) describes; the aux table shows the ranks, pairs and the suffix array after each round. In the Kasai part, green cells are the letters the two neighbouring suffixes share.

Rung 3: radix sort the pairs,

The ranks are integers in , and the keys are pairs of such integers. Pairs of small integers do not need a comparison sort: sort by the second number with a counting sort, then by the first number with a stable counting sort. That is radix sort with two digits (see Non-Comparison Sorts). Each pass is , so each round is and the total is .

There is a neat shortcut for the first pass. We need the positions ordered by their second key, :

  • Positions with have second key , the smallest; put them first.
  • For the rest, the order by is the order of in the previous suffix array (it is sorted by rank!). So walk the old , and for each entry output .

No counting needed for the second key at all. Then one stable counting sort by finishes the round:

ROUND(k):
    second = [n-k, n-k+1, ..., n-1] + [p - k for p in sa if p >= k]
    counting-sort `second` by rank[i], stably  ->  new sa
    walk new sa; new rank increases when (rank[i], rank[i+k]) changes

The stability matters: within a group of equal first keys, the counting sort keeps the order of second, which is already sorted by the second key. That is exactly the lexicographic order on pairs.

Measured with the C++ implementation below (Apple M5, -O2): random 26-letter text of length builds in about 23 ms, plus about 7 ms for the LCP array. All-a text of the same length needs the full rounds and takes about 95 ms (LCP 1.6 ms). At length , all-a takes 8 ms, against roughly 300 ms for the naive sort.

Rung 4: linear time (SA-IS, DC3)

Two famous algorithms build the suffix array in for integer alphabets:

  • DC3 / skew algorithm — Juha Kärkkäinen and Peter Sanders, "Simple linear work suffix array construction", ICALP 2003 (journal version with Stefan Burkhardt in Journal of the ACM 53(6), 2006). Sort the suffixes at positions recursively (by turning triples of letters into single "letters" of a string two-thirds as long), then sort the suffixes with one radix pass, then merge. .
  • SA-IS (induced sorting) — Ge Nong, Sen Zhang and Wai Hong Chan, "Linear suffix array construction by almost pure induced-sorting", Data Compression Conference (DCC) 2009. Classify each suffix as S-type (smaller than the next suffix) or L-type (larger), sort only the "leftmost S" (LMS) suffixes, recursively if needed, then induce the order of everything else with two linear scans. It is the fastest linear-time method in practice and is what serious libraries use: the AtCoder Library's suffix_array is SA-IS (with naive and doubling fallbacks for very short strings), and Yuta Mori's sais and libdivsufsort libraries are the standard C implementations.

You almost never need to write SA-IS in a contest: doubling handles comfortably in C++ (above). Know that linear construction exists, what the two names mean, and why: SA-IS makes construction no more expensive than reading the input.

The ladder at a glance

RungMethodTimeExtra spaceTypical use
1Sort suffixes as strings worst, near on random text (careful: slicing copies cost )Interviews,
2Doubling + comparison sortQuick to write,
3Doubling + radix sortContest default,
4SA-IS / DC3Libraries, genomes, compressors

Each rung removes one waste: rung 2 stops comparing letters one at a time (ranks summarise letters in one number); rung 3 stops using comparisons to sort small integers; rung 4 stops redoing the whole sort times.

The LCP array: Kasai's algorithm

The suffix array alone tells you the order. Most applications also need to know how much neighbouring suffixes share. Computing by comparing and letter by letter costs per pair, total on repetitive strings.

Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa and Kunsoo Park ("Linear-time longest-common-prefix computation in suffix arrays and its applications", CPM 2001) noticed that if you visit the suffixes in text order (suffix 0, then 1, then 2, …) instead of sorted order, the LCP value can only drop by at most one from one suffix to the next. So you carry the previous value , subtract one, and only extend from there.

KASAI(s, sa):
    rank[sa[j]] = j for all j
    h = 0
    for i = 0 .. n-1:                 # suffixes in TEXT order
        if rank[i] == 0: h = 0; continue
        j = sa[rank[i] - 1]           # the suffix just before i in sorted order
        while s[i + h] == s[j + h]: h += 1
        lcp[rank[i]] = h
        if h > 0: h -= 1              # the next suffix keeps at least h - 1

Kasai trace on banana

, .

suffix predecessor in sorted order at startletters compared foundwrite carried
0banana31 (anana)0b vs a ✗00
1anana23 (ana)0a ✓ n ✓ a ✓, then ana ends32
2nana54 (na)2 (free)na ends at once21
3ana15 (a)1 (free)a ends at once10
4na40 (banana)0n vs b ✗00
5a0— (first)————0

Result: . Look at row 2: we already knew anana and ana share ana. Chop the first letter off both and you get nana and na, which must share na. So when we reach suffix 2 we start at for free and only check whether the match continues.

Correctness

Claim 1: prefix doubling sorts correctly

Write for the first letters of suffix (fewer if the suffix is shorter). Invariant: after the round that sets , exactly when , and exactly when .

Base. For the ranks are the letters' order. True.

Step. (concatenation), where is empty when . Lexicographic order on a concatenation of two "blocks" is: compare first blocks; if equal, compare second blocks. That is exactly the order on pairs , with the empty block mapped to , below every real rank. One subtlety: when first blocks are equal and have length , both second blocks start right after, so comparing them is valid; when first blocks are equal but shorter than , both suffixes have ended, so they are the same suffix. Sorting by the pair and re-numbering equal pairs equally keeps the invariant for .

Termination. All suffixes have different lengths, so for all differ and all ranks are distinct; the loop stops after at most rounds. It can stop earlier, as on banana.

Claim 2: the second-key shortcut is a correct sort

The list [n-k .. n-1] + [p - k for p in sa if p >= k] contains each position once. The first group has key . In the second group, position has second key , and the old lists in non-decreasing rank order. So the list is sorted by second key; a stable sort by first key then yields pair order.

Claim 3 (Kasai): drops by at most one

Let suffix have predecessor in sorted order and . Then:

  1. Suffixes and start with the same letter , and in sorted order. Removing from both does not change their order (the comparison is decided at the same later position), so suffix comes before suffix in sorted order, and .
  2. Let be the predecessor of suffix in sorted order. Suffix is at or before . A key fact about sorted lists of strings: the LCP of two strings is the minimum of the LCPs of all adjacent pairs between them (if every neighbour pair shares letters, then the first letters are constant along the block). Equivalently, a string sorted between two strings shares at least as long a prefix with each as they share with each other. Since lies between and , .

So the true LCP for suffix is at least , and starting the scan at skips only letters that are known to match.

Running time. starts at 0 and never exceeds . It goes down in only two ways: the h -= 1 (at most once per iteration, so at most times in total) and the single reset at the suffix of rank 0 (which loses at most ). Every successful letter comparison raises by one. Rises minus falls equals the final value of , which is at most , so total rises . Each iteration also makes at most one failing comparison. So Kasai does at most about letter comparisons: . This is the same "staircase" amortisation as in KMP.

Claim 4: distinct substrings

Every distinct substring is a prefix of at least one suffix. Assign each distinct substring to the first suffix in sorted order that has it as a prefix. Suffix has non-empty prefixes. Which of them already belonged to an earlier suffix? A prefix of length also prefixes some earlier suffix iff it prefixes the immediately previous one (by the "minimum over neighbours" fact in Claim 3, the earlier suffix sharing the most with is ), iff . So suffix contributes exactly new substrings. Summing over , .

Complexity

StepTimeExtra spaceNotes
Naive SA worstFine on random text; dies on aaaa…
Doubling + sort
Doubling + radix, about 5 integer arrays rounds; best case 1–2 rounds on random text over a large alphabet
SA-IS / DC3Integer alphabet of size
Kasai LCP, at most about letter comparisons for rank + lcp
Pattern count, binary search with LCP-LR arrays (Manber–Myers)
Sparse table on LCP buildThen any in

Memory in real units. With 32-bit integers: the text (1 byte per letter for ASCII or DNA), (4 bytes), and, while building or querying LCP, and (4 bytes each). So about bytes for a bare suffix array and – bytes during LCP work. For a 3.1-billion-letter genome, positions exceed , so you need 40- or 64-bit entries, and alone is 12–25 GB. That pressure is exactly why the compressed FM-index (below) took over in genomics.

Best, average, worst. Doubling stops as soon as all ranks differ, which happens once exceeds the longest repeated substring. On random text over 26 letters that is about letters, so only a handful of rounds; on aaaa…a it is the full . Hence 23 ms vs 95 ms in the measurement above.

Implementation

Prefix doubling with radix (counting) sort, Kasai's LCP, distinct substrings, longest repeated substring, and occurrence counting by binary search. Every snippet checks banana and mississippi by hand-verified values, then compares against brute force (sorting suffixes, counting substrings with a set) on 2,000 random strings over {a, b}, where bugs show up fastest. All four were run: Python 3.12, Java 21, g++ (-std=c++17 -O2 -Wall), and Node 24 (type stripping).

def suffix_array(s: str) -> list[int]:
    """Prefix doubling with counting (radix) sort: O(n log n)."""
    n = len(s)
    if n == 0:
        return []
    # Round 0: rank by the first character, compressed to 0..r-1.
    chars = sorted(set(s))
    code = {c: i for i, c in enumerate(chars)}
    rank = [code[c] for c in s]
    sa = sorted(range(n), key=lambda i: rank[i])
    classes = len(chars)
    tmp = [0] * n
    k = 1
    while classes < n:
        # 1) Order by the SECOND key: suffixes with i + k >= n (key -1) come first,
        #    then the rest in the order of their second half, which is sa shifted by k.
        second = [i for i in range(n - k, n)] + [p - k for p in sa if p >= k]
        # 2) Stable counting sort of that list by the FIRST key, rank[i].
        cnt = [0] * (classes + 1)
        for r in rank:
            cnt[r + 1] += 1
        for c in range(classes):
            cnt[c + 1] += cnt[c]          # cnt[c] = first slot for class c
        for p in second:
            sa[cnt[rank[p]]] = p
            cnt[rank[p]] += 1
        # 3) New ranks: neighbours with equal (first, second) pairs share a rank.
        def key(i: int) -> tuple[int, int]:
            return (rank[i], rank[i + k] if i + k < n else -1)
        tmp[sa[0]] = 0
        for j in range(1, n):
            tmp[sa[j]] = tmp[sa[j - 1]] + (key(sa[j]) != key(sa[j - 1]))
        rank, tmp = tmp, rank
        classes = rank[sa[-1]] + 1
        k *= 2
    return sa


def lcp_kasai(s: str, sa: list[int]) -> list[int]:
    """lcp[i] = LCP(suffix sa[i-1], suffix sa[i]); lcp[0] = 0. O(n)."""
    n = len(s)
    rank = [0] * n
    for i, p in enumerate(sa):
        rank[p] = i
    lcp = [0] * n
    h = 0
    for i in range(n):                       # suffixes in TEXT order
        if rank[i] == 0:
            h = 0
            continue
        j = sa[rank[i] - 1]                  # the suffix just before i in sorted order
        while i + h < n and j + h < n and s[i + h] == s[j + h]:
            h += 1
        lcp[rank[i]] = h
        if h > 0:
            h -= 1                           # the next suffix keeps at least h - 1
    return lcp


def distinct_substrings(s: str) -> int:
    n = len(s)
    return n * (n + 1) // 2 - sum(lcp_kasai(s, suffix_array(s)))


def longest_repeated(s: str) -> str:
    sa = suffix_array(s)
    lcp = lcp_kasai(s, sa)
    best = max(range(len(s)), key=lambda i: lcp[i], default=0)
    return s[sa[best]:sa[best] + lcp[best]] if s else ""


def count_occurrences(s: str, sa: list[int], p: str) -> int:
    """Binary search for the block of suffixes that start with p: O(m log n)."""
    m = len(p)
    lo, hi = 0, len(sa)                      # first suffix whose m-prefix >= p
    while lo < hi:
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + m] < p:
            lo = mid + 1
        else:
            hi = mid
    first = lo
    hi = len(sa)                             # first suffix whose m-prefix > p
    while lo < hi:
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + m] <= p:
            lo = mid + 1
        else:
            hi = mid
    return lo - first


if __name__ == "__main__":
    import random
    s = "banana"
    sa = suffix_array(s)
    assert sa == [5, 3, 1, 0, 4, 2]
    assert lcp_kasai(s, sa) == [0, 1, 3, 0, 0, 2]
    assert distinct_substrings(s) == 15
    assert longest_repeated(s) == "ana"
    assert count_occurrences(s, sa, "ana") == 2
    assert count_occurrences(s, sa, "nab") == 0
    assert suffix_array("mississippi") == [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2]
    assert distinct_substrings("aaaa") == 4
    rng = random.Random(1)
    for _ in range(2000):                    # compare with the naive definition
        t = "".join(rng.choice("ab") for _ in range(rng.randint(1, 30)))
        assert suffix_array(t) == sorted(range(len(t)), key=lambda i: t[i:])
        assert distinct_substrings(t) == len({t[i:j] for i in range(len(t)) for j in range(i + 1, len(t) + 1)})
    print("python ok")
import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class SuffixArray {
    /** Prefix doubling with counting (radix) sort: O(n log n). */
    static int[] suffixArray(String s) {
        int n = s.length();
        if (n == 0) return new int[0];
        int[] rank = new int[n], sa = new int[n], tmp = new int[n], second = new int[n];
        // Round 0: rank by the first character (counting sort over char codes).
        int[] cnt = new int[Math.max(n, 65536) + 1];
        for (int i = 0; i < n; i++) cnt[s.charAt(i) + 1]++;
        for (int c = 0; c < 65536; c++) cnt[c + 1] += cnt[c];
        for (int i = 0; i < n; i++) sa[cnt[s.charAt(i)]++] = i;
        int classes = 1;
        rank[sa[0]] = 0;
        for (int j = 1; j < n; j++) {
            if (s.charAt(sa[j]) != s.charAt(sa[j - 1])) classes++;
            rank[sa[j]] = classes - 1;
        }
        for (int k = 1; classes < n; k *= 2) {
            // 1) Order by the second key: i + k >= n first (key -1), then sa shifted by k.
            int t = 0;
            for (int i = n - k; i < n; i++) second[t++] = i;
            for (int j = 0; j < n; j++) if (sa[j] >= k) second[t++] = sa[j] - k;
            // 2) Stable counting sort by the first key.
            Arrays.fill(cnt, 0, classes + 1, 0);
            for (int i = 0; i < n; i++) cnt[rank[i] + 1]++;
            for (int c = 0; c < classes; c++) cnt[c + 1] += cnt[c];
            for (int j = 0; j < n; j++) sa[cnt[rank[second[j]]]++] = second[j];
            // 3) New ranks: equal (first, second) pairs share a rank.
            tmp[sa[0]] = 0;
            for (int j = 1; j < n; j++) {
                int a = sa[j - 1], b = sa[j];
                int a2 = a + k < n ? rank[a + k] : -1, b2 = b + k < n ? rank[b + k] : -1;
                tmp[b] = tmp[a] + ((rank[a] != rank[b] || a2 != b2) ? 1 : 0);
            }
            int[] swap = rank; rank = tmp; tmp = swap;
            classes = rank[sa[n - 1]] + 1;
        }
        return sa;
    }

    /** lcp[i] = LCP(suffix sa[i-1], suffix sa[i]); lcp[0] = 0. Kasai, O(n). */
    static int[] lcpKasai(String s, int[] sa) {
        int n = s.length();
        int[] rank = new int[n], lcp = new int[n];
        for (int i = 0; i < n; i++) rank[sa[i]] = i;
        int h = 0;
        for (int i = 0; i < n; i++) {                 // suffixes in TEXT order
            if (rank[i] == 0) { h = 0; continue; }
            int j = sa[rank[i] - 1];                  // previous suffix in sorted order
            while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) h++;
            lcp[rank[i]] = h;
            if (h > 0) h--;                           // next suffix keeps at least h - 1
        }
        return lcp;
    }

    static long distinctSubstrings(String s) {
        long n = s.length(), total = n * (n + 1) / 2;
        for (int v : lcpKasai(s, suffixArray(s))) total -= v;
        return total;
    }

    static String longestRepeated(String s) {
        int[] sa = suffixArray(s), lcp = lcpKasai(s, sa);
        int best = 0;
        for (int i = 1; i < lcp.length; i++) if (lcp[i] > lcp[best]) best = i;
        return s.isEmpty() ? "" : s.substring(sa[best], sa[best] + lcp[best]);
    }

    /** Compare the first p.length() chars of suffix i with p: <0, 0, >0. */
    static int cmpPrefix(String s, int i, String p) {
        int m = p.length();
        for (int d = 0; d < m; d++) {
            if (i + d == s.length()) return -1;       // suffix ran out: it is smaller
            int c = Character.compare(s.charAt(i + d), p.charAt(d));
            if (c != 0) return c;
        }
        return 0;
    }

    /** Number of occurrences of p: two binary searches, O(m log n). */
    static int countOccurrences(String s, int[] sa, String p) {
        int lo = 0, hi = sa.length;
        while (lo < hi) { int mid = (lo + hi) >>> 1; if (cmpPrefix(s, sa[mid], p) < 0) lo = mid + 1; else hi = mid; }
        int first = lo;
        hi = sa.length;
        while (lo < hi) { int mid = (lo + hi) >>> 1; if (cmpPrefix(s, sa[mid], p) <= 0) lo = mid + 1; else hi = mid; }
        return lo - first;
    }

    static Integer[] naive(String s) {
        Integer[] idx = new Integer[s.length()];
        for (int i = 0; i < idx.length; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> s.substring(a).compareTo(s.substring(b)));
        return idx;
    }

    public static void main(String[] args) {
        String s = "banana";
        int[] sa = suffixArray(s);
        check(Arrays.equals(sa, new int[]{5, 3, 1, 0, 4, 2}));
        check(Arrays.equals(lcpKasai(s, sa), new int[]{0, 1, 3, 0, 0, 2}));
        check(distinctSubstrings(s) == 15);
        check(longestRepeated(s).equals("ana"));
        check(countOccurrences(s, sa, "ana") == 2 && countOccurrences(s, sa, "nab") == 0);
        check(Arrays.equals(suffixArray("mississippi"), new int[]{10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2}));
        check(distinctSubstrings("aaaa") == 4);
        Random rng = new Random(1);
        for (int it = 0; it < 2000; it++) {           // compare with the naive definition
            StringBuilder b = new StringBuilder();
            int len = 1 + rng.nextInt(30);
            for (int i = 0; i < len; i++) b.append(rng.nextBoolean() ? 'a' : 'b');
            String t = b.toString();
            check(Arrays.equals(Arrays.stream(suffixArray(t)).boxed().toArray(Integer[]::new), naive(t)));
            Set<String> subs = new HashSet<>();
            for (int i = 0; i < len; i++) for (int j = i + 1; j <= len; j++) subs.add(t.substring(i, j));
            check(distinctSubstrings(t) == subs.size());
        }
        System.out.println("java ok");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <string>
#include <vector>
using namespace std;

// Prefix doubling with counting (radix) sort: O(n log n).
vector<int> suffixArray(const string& s) {
    int n = (int)s.size();
    if (n == 0) return {};
    vector<int> sa(n), rank(n), tmp(n), second(n), cnt(max(n, 256) + 1, 0);
    // Round 0: rank by the first byte (counting sort over 0..255).
    for (unsigned char c : s) cnt[c + 1]++;
    for (int c = 0; c < 256; c++) cnt[c + 1] += cnt[c];
    for (int i = 0; i < n; i++) sa[cnt[(unsigned char)s[i]]++] = i;
    int classes = 1;
    rank[sa[0]] = 0;
    for (int j = 1; j < n; j++) {
        if (s[sa[j]] != s[sa[j - 1]]) classes++;
        rank[sa[j]] = classes - 1;
    }
    for (int k = 1; classes < n; k *= 2) {
        // 1) Order by the second key: i + k >= n first (key -1), then sa shifted by k.
        int t = 0;
        for (int i = n - k; i < n; i++) second[t++] = i;
        for (int j = 0; j < n; j++) if (sa[j] >= k) second[t++] = sa[j] - k;
        // 2) Stable counting sort by the first key.
        fill(cnt.begin(), cnt.begin() + classes + 1, 0);
        for (int i = 0; i < n; i++) cnt[rank[i] + 1]++;
        for (int c = 0; c < classes; c++) cnt[c + 1] += cnt[c];
        for (int j = 0; j < n; j++) sa[cnt[rank[second[j]]]++] = second[j];
        // 3) New ranks: equal (first, second) pairs share a rank.
        tmp[sa[0]] = 0;
        for (int j = 1; j < n; j++) {
            int a = sa[j - 1], b = sa[j];
            int a2 = a + k < n ? rank[a + k] : -1, b2 = b + k < n ? rank[b + k] : -1;
            tmp[b] = tmp[a] + ((rank[a] != rank[b] || a2 != b2) ? 1 : 0);
        }
        swap(rank, tmp);
        classes = rank[sa[n - 1]] + 1;
    }
    return sa;
}

// lcp[i] = LCP(suffix sa[i-1], suffix sa[i]); lcp[0] = 0. Kasai, O(n).
vector<int> lcpKasai(const string& s, const vector<int>& sa) {
    int n = (int)s.size();
    vector<int> rank(n), lcp(n, 0);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    int h = 0;
    for (int i = 0; i < n; i++) {                 // suffixes in TEXT order
        if (rank[i] == 0) { h = 0; continue; }
        int j = sa[rank[i] - 1];                  // previous suffix in sorted order
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
        lcp[rank[i]] = h;
        if (h > 0) h--;                           // next suffix keeps at least h - 1
    }
    return lcp;
}

long long distinctSubstrings(const string& s) {
    long long n = (long long)s.size(), total = n * (n + 1) / 2;
    for (int v : lcpKasai(s, suffixArray(s))) total -= v;
    return total;
}

string longestRepeated(const string& s) {
    if (s.empty()) return "";
    vector<int> sa = suffixArray(s), lcp = lcpKasai(s, sa);
    int best = (int)(max_element(lcp.begin(), lcp.end()) - lcp.begin());
    return s.substr(sa[best], lcp[best]);
}

// Number of occurrences of p: two binary searches, O(m log n).
int countOccurrences(const string& s, const vector<int>& sa, const string& p) {
    auto prefixLess = [&](int i, const string& q) { return s.compare(i, q.size(), q) < 0; };
    auto lo = lower_bound(sa.begin(), sa.end(), p, prefixLess);
    auto hi = upper_bound(lo, sa.end(), p, [&](const string& q, int i) { return s.compare(i, q.size(), q) > 0; });
    return (int)(hi - lo);
}

int main() {
    string s = "banana";
    vector<int> sa = suffixArray(s);
    assert(sa == vector<int>({5, 3, 1, 0, 4, 2}));
    assert(lcpKasai(s, sa) == vector<int>({0, 1, 3, 0, 0, 2}));
    assert(distinctSubstrings(s) == 15);
    assert(longestRepeated(s) == "ana");
    assert(countOccurrences(s, sa, "ana") == 2 && countOccurrences(s, sa, "nab") == 0);
    assert(suffixArray("mississippi") == vector<int>({10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2}));
    assert(distinctSubstrings("aaaa") == 4);
    mt19937 rng(1);
    for (int it = 0; it < 2000; it++) {           // compare with the naive definition
        int len = 1 + (int)(rng() % 30);
        string t;
        for (int i = 0; i < len; i++) t += (rng() & 1) ? 'a' : 'b';
        vector<int> want(len);
        for (int i = 0; i < len; i++) want[i] = i;
        sort(want.begin(), want.end(), [&](int a, int b) { return t.substr(a) < t.substr(b); });
        assert(suffixArray(t) == want);
        set<string> subs;
        for (int i = 0; i < len; i++) for (int j = i + 1; j <= len; j++) subs.insert(t.substr(i, j - i));
        assert(distinctSubstrings(t) == (long long)subs.size());
    }
    cout << "c++ ok" << endl;
    return 0;
}
/** Prefix doubling with counting (radix) sort: O(n log n). */
function suffixArray(s: string): number[] {
  const n = s.length;
  if (n === 0) return [];
  const sa = new Int32Array(n), second = new Int32Array(n);
  let rank = new Int32Array(n), next = new Int32Array(n);
  // Round 0: rank by the first UTF-16 code unit (counting sort over 0..65535).
  const cnt = new Int32Array(Math.max(n, 65536) + 1);
  for (let i = 0; i < n; i++) cnt[s.charCodeAt(i) + 1]++;
  for (let c = 0; c < 65536; c++) cnt[c + 1] += cnt[c];
  for (let i = 0; i < n; i++) sa[cnt[s.charCodeAt(i)]++] = i;
  let classes = 1;
  rank[sa[0]] = 0;
  for (let j = 1; j < n; j++) {
    if (s[sa[j]] !== s[sa[j - 1]]) classes++;
    rank[sa[j]] = classes - 1;
  }
  for (let k = 1; classes < n; k *= 2) {
    // 1) Order by the second key: i + k >= n first (key -1), then sa shifted by k.
    let t = 0;
    for (let i = n - k; i < n; i++) second[t++] = i;
    for (let j = 0; j < n; j++) if (sa[j] >= k) second[t++] = sa[j] - k;
    // 2) Stable counting sort by the first key.
    cnt.fill(0, 0, classes + 1);
    for (let i = 0; i < n; i++) cnt[rank[i] + 1]++;
    for (let c = 0; c < classes; c++) cnt[c + 1] += cnt[c];
    for (let j = 0; j < n; j++) sa[cnt[rank[second[j]]]++] = second[j];
    // 3) New ranks: equal (first, second) pairs share a rank.
    next[sa[0]] = 0;
    for (let j = 1; j < n; j++) {
      const a = sa[j - 1], b = sa[j];
      const a2 = a + k < n ? rank[a + k] : -1, b2 = b + k < n ? rank[b + k] : -1;
      next[b] = next[a] + (rank[a] !== rank[b] || a2 !== b2 ? 1 : 0);
    }
    [rank, next] = [next, rank];
    classes = rank[sa[n - 1]] + 1;
  }

  return Array.from(sa);
}

/** lcp[i] = LCP(suffix sa[i-1], suffix sa[i]); lcp[0] = 0. Kasai, O(n). */
function lcpKasai(s: string, sa: number[]): number[] {
  const n = s.length;
  const rank = new Array<number>(n), lcp = new Array<number>(n).fill(0);
  for (let i = 0; i < n; i++) rank[sa[i]] = i;
  let h = 0;
  for (let i = 0; i < n; i++) { // suffixes in TEXT order
    if (rank[i] === 0) { h = 0; continue; }
    const j = sa[rank[i] - 1]; // previous suffix in sorted order
    while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
    lcp[rank[i]] = h;
    if (h > 0) h--; // next suffix keeps at least h - 1
  }
  return lcp;
}

function distinctSubstrings(s: string): number {
  const n = s.length;
  return (n * (n + 1)) / 2 - lcpKasai(s, suffixArray(s)).reduce((a, b) => a + b, 0);
}

function longestRepeated(s: string): string {
  if (s.length === 0) return "";
  const sa = suffixArray(s), lcp = lcpKasai(s, sa);
  let best = 0;
  for (let i = 1; i < lcp.length; i++) if (lcp[i] > lcp[best]) best = i;
  return s.slice(sa[best], sa[best] + lcp[best]);
}

/** Number of occurrences of p: two binary searches, O(m log n). */
function countOccurrences(s: string, sa: number[], p: string): number {
  const m = p.length;
  const pre = (i: number): string => s.slice(sa[i], sa[i] + m);
  let lo = 0, hi = sa.length;
  while (lo < hi) { const mid = (lo + hi) >> 1; if (pre(mid) < p) lo = mid + 1; else hi = mid; }
  const first = lo;
  hi = sa.length;
  while (lo < hi) { const mid = (lo + hi) >> 1; if (pre(mid) <= p) lo = mid + 1; else hi = mid; }
  return lo - first;
}

function check(ok: boolean, what: string): void {
  if (!ok) throw new Error(what);
}
const same = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);
const sa0 = suffixArray("banana");
check(same(sa0, [5, 3, 1, 0, 4, 2]), "sa");
check(same(lcpKasai("banana", sa0), [0, 1, 3, 0, 0, 2]), "lcp");
check(distinctSubstrings("banana") === 15, "distinct");
check(longestRepeated("banana") === "ana", "repeated");
check(countOccurrences("banana", sa0, "ana") === 2 && countOccurrences("banana", sa0, "nab") === 0, "count");
check(same(suffixArray("mississippi"), [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2]), "mississippi");
check(distinctSubstrings("aaaa") === 4, "aaaa");
let seed = 1;
const rand = (): number => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
for (let it = 0; it < 2000; it++) { // compare with the naive definition
  const len = 1 + Math.floor(rand() * 30);
  let t = "";
  for (let i = 0; i < len; i++) t += rand() < 0.5 ? "a" : "b";
  const want = Array.from({ length: len }, (_, i) => i).sort((a, b) => (t.slice(a) < t.slice(b) ? -1 : 1));
  check(same(suffixArray(t), want), "random sa " + t);
  const subs = new Set<string>();
  for (let i = 0; i < len; i++) for (let j = i + 1; j <= len; j++) subs.add(t.slice(i, j));
  check(distinctSubstrings(t) === subs.size, "random distinct " + t);
}
console.log("ts ok");

Notes on the code:

  • The initial ranks. Python compresses the characters it sees; Java and TypeScript count over all 65,536 UTF-16 code units; C++ counts over 256 byte values. Any order-preserving numbering works.
  • No sentinel. Many contest templates append a $ (or \0) and sort cyclic shifts, which makes wrap around. This version uses the "past the end = −1" key instead, so the input can contain any character and the output has exactly entries.
  • Python slicing in the binary search copies up to characters per step, which is the comparison cost anyway; for a hot loop compare in place.
  • Overflow. exceeds for ; the Java and C++ versions use 64-bit long/long long. TypeScript numbers are exact up to , which is enough for up to about .

Applications

1. Pattern search in

All suffixes that start with (length ) form one contiguous block of the suffix array. Find its left end with a lower-bound binary search ("first suffix whose first letters are ") and its right end with an upper-bound search ("first suffix whose first letters are "). The block size is the number of occurrences; the entries in the block are their positions. Each step compares up to letters, and there are steps.

Trace for = ana in banana ():

searchlohimidfirst 3 letters of suffix decision
lower063banban ≥ ana: hi = 3
lower031ana≥: hi = 1
lower010aa < ana: lo = 1 → first = 1
upper163ban> ana: hi = 3
upper132ana≤: lo = 3 → end = 3

Block , two occurrences, at positions and . Manber and Myers showed how to reach by also storing the LCP of each binary-search midpoint with its interval ends (the "LCP-LR" arrays), so that the search never re-compares letters it already knows match. In practice is usually fine.

2. Number of distinct substrings

, proved in Claim 4. For banana: 21 − 6 = 15. For mississippi: 66 − 13 = 53. This is CSES "Distinct Substrings" and SPOJ DISUBSTR in one line after the two arrays.

3. Longest repeated substring

The longest substring occurring at least twice (overlaps allowed) is the longest common prefix of some two suffixes, and the pair with the longest common prefix is always adjacent in sorted order (Claim 3's neighbour fact). So the answer is , read from . banana → ana; mississippi → issi (positions 1 and 4). LeetCode 1044 asks exactly this; the hashing lesson solves it with binary search plus hashing and warns about collisions. The suffix array answer is deterministic.

At least times: a substring occurs times iff consecutive suffixes share it, so the answer is the maximum, over all windows of consecutive LCP values, of the window's minimum. A sliding-window minimum (monotonic deque) makes this .

Without overlap: "longest substring that occurs twice without overlapping" needs both an LCP of at least and starting positions at least apart. Binary search on , then scan blocks of consecutive suffixes with and check in each block.

4. Longest common substring of two strings

Glue the strings with a separator that occurs in neither, , and build the suffix array of . A common substring of and is a common prefix of a suffix starting in and a suffix starting in . The separator stops any common prefix from running across from into (it is unique, so two different suffixes can never both have it at the same offset). As before, the best pair is adjacent somewhere in sorted order, so:

Example: = banana, = cabana, = banana#cabana. Part of the sorted list:

suffixfrom
61anana#cabanaA3
79banaB0
80banana#cabanaA4
97cabanaB0

Rows 7 and 8 come from different strings and share bana: the longest common substring has length 4. (Row 6 has lcp 3 with row 5, ana#cabana, but both of those are from A.) For strings, use distinct separators and a sliding window over the suffix array that covers all colours: that is SPOJ LCS2-type problems, and also what a generalized suffix tree does (next lessons).

5. The -th smallest distinct substring

Distinct substrings in lexicographic order are: for each suffix in sorted order, its prefixes of lengths , in increasing length. (Shorter prefixes are smaller; and every prefix of length was listed already.) So walk the suffix array, subtract each suffix's count of new substrings from until it fits.

For banana:

suffixnew substrings (in order)countrunning total
0aa11
1anaan, ana23
2ananaanan, anana25
3bananab … banana611
4nan, na213
5nananan, nana215

The 5th smallest is anana; the 7th is ba (row 3, second new prefix). That is CSES "Substring Order I". If repeats count ("Substring Order II"), each prefix of length of suffix is counted once per occurrence, which needs the LCP block structure (or a suffix automaton with occurrence counts).

6. LCP of any two suffixes in via RMQ

For suffixes at sorted positions :

That is the "minimum over neighbours" fact again. A range minimum query (RMQ) structure answers this in after preprocessing, using a sparse table. Example: suffixes 5 (a, rank 0) and 1 (anana, rank 2): . Indeed they share only a.

This one tool unlocks a lot: compare any two substrings lexicographically in (LCP of their suffixes, capped by their lengths, then one letter); count palindromes by matching with its reverse; find "longest common extension" for approximate matching with mismatches in jumps per position (the "kangaroo" method). It is the deterministic replacement for "binary search + hashing" whenever you cannot risk collisions.

7. The Burrows–Wheeler transform and the FM-index

Append a unique smallest character $ and write down the letter before each suffix in sorted order (wrapping around). For banana$, and

Equivalently, sort all rotations of banana$ and take the last column ($banana, a$banan, ana$ban, anana$b, banana$, na$bana, nana$ba). Michael Burrows and David Wheeler published it in 1994 (DEC SRC Research Report 124) as a compression pre-step. Two properties make it remarkable:

  1. It groups letters. Letters that come before similar contexts end up next to each other (all the as before na… cluster), so the BWT has long runs and compresses well with move-to-front plus entropy coding.
  2. It is invertible, using only the BWT itself (the "LF mapping": the -th occurrence of letter in the last column is the -th occurrence of in the first column).

Paolo Ferragina and Giovanni Manzini ("Opportunistic data structures with applications", FOCS 2000) showed that the BWT plus small rank tables supports backward search: count occurrences of in rank queries by extending the pattern one letter at a time from the right, keeping the suffix-array interval of the current suffix of . Store a sampled suffix array to recover positions. The result, the FM-index, is a compressed full-text index often smaller than the text itself. It is the engine of the short-read aligners BWA (Heng Li and Richard Durbin, Bioinformatics 25(14), 2009) and Bowtie (Ben Langmead et al., Genome Biology 10:R25, 2009), which index a 3-gigabase human genome in a few gigabytes. Computing the BWT is computing a suffix array; that is why fast SA construction matters so much in bioinformatics.

Real-world uses

  • Compression: bzip2. Julian Seward's bzip2 applies the Burrows–Wheeler transform to blocks of 100–900 kB (the -1 … -9 flags), then move-to-front, run-length and Huffman coding. Sorting the rotations of each block is a suffix-sorting problem; bzip2 uses its own block-sorting code with a fallback for highly repetitive blocks, which are exactly the inputs where naive suffix comparison degenerates.
  • Genome indexing and read alignment. BWA and Bowtie (above) build an FM-index of the reference genome once; each of hundreds of millions of 100–150-letter sequencing reads is then located by backward search. Earlier whole-genome comparison tools used suffix trees (MUMmer 1–3); MUMmer4 (Marçais et al., PLOS Computational Biology, 2018) switched to a suffix array to cut memory. Enhanced suffix arrays (suffix array + LCP + child tables) were introduced precisely to replace suffix trees in such tools: Abouelhoda, Kurtz and Ohlebusch, "Replacing suffix trees with enhanced suffix arrays", Journal of Discrete Algorithms 2(1), 2004.
  • Deduplicating language-model training data. Lee et al., "Deduplicating Training Data Makes Language Models Better" (ACL 2022), built a suffix array over the C4 corpus (hundreds of GB of text) to find every repeated span of at least 50 tokens, which is the "longest repeated substring" application at scale. The infini-gram project (Liu et al., 2024) uses suffix arrays over trillions of tokens to answer n-gram count queries for arbitrary by binary search.
  • Libraries. libdivsufsort (Yuta Mori) is a widely used fast suffix sorter in C; the AtCoder Library ships suffix_array (SA-IS) and lcp_array (Kasai) for contest use; the SDSL-lite C++ library provides compressed suffix arrays and FM-indexes.
  • Plagiarism and code-clone detection, data-diffing. Finding long common substrings between many documents or source files is the generalized LCS application above; suffix-array-based clone detectors use exactly the "adjacent suffixes from different files with large LCP" scan.

Pitfalls & edge cases

  • Off-by-one in LCP indexing. In this lesson compares and , with . Some libraries (AtCoder's lcp_array) return values where entry compares and . Mixing conventions shifts every answer by one row.
  • Forgetting the for "past the end". Without it, a and ab can be treated as equal after one round, or you read rank[i + k] out of bounds. Either add the explicit check, or append a sentinel smaller than every letter and use cyclic shifts.
  • Separator not unique or not smaller. For LCS of and , the separator must not occur in either string. If you join strings, use different separators (or tag each suffix with its string id), otherwise a common prefix can run through # from one string into another.
  • Not resetting at rank 0. In Kasai, the suffix with rank 0 has no predecessor; set there. Carrying a stale forward reports LCPs that are too long.
  • Recomputing counting-sort sizes. The counting array must cover all rank values; after round 0, ranks are in . Initial character codes need a bigger array (256 bytes, or 65,536 for UTF-16), or compress the alphabet first.
  • Integer overflow in the substring count. for is about , beyond 32-bit.
  • Python and Java substring slicing. s[i:] copies; sorting [s[i:] for i in range(n)] allocates characters. For the naive method sort indices with a key or comparator, and still expect worst case.
  • Unicode. Lexicographic order on UTF-16 code units (Java, JavaScript) differs from code-point order for characters outside the Basic Multilingual Plane. For an index over bytes (UTF-8) both sides must agree on the encoding.
  • Stopping too late. Looping exactly times is correct but wastes rounds; stop as soon as the number of rank classes equals .

Variations

  • Cyclic suffix array (sorting rotations). Append nothing and let wrap modulo : you sort the rotations. Used for the BWT and for "lexicographically smallest rotation" (the first entry). A dedicated lesson covers the Booth and Lyndon-factorisation approaches: Minimal Rotation & Lyndon Words.
  • Enhanced suffix array. Suffix array + LCP + "child table" simulates every suffix-tree traversal (top-down, bottom-up, suffix links) with less memory (Abouelhoda–Kurtz–Ohlebusch 2004). Bottom-up traversal of the LCP intervals with a stack is how you solve "for each distinct repeated substring, how many times does it occur" problems.
  • Compressed suffix arrays and the FM-index. Store the suffix array in bits or less (Grossi–Vitter, Sadakane, Ferragina–Manzini); query time grows by polylog factors. See Navarro and Mäkinen, "Compressed full-text indexes", ACM Computing Surveys 39(1), 2007.
  • Sparse suffix arrays. Index only every -th suffix (or only word starts) to cut memory; queries must try alignments. Common in text search engines where only word-start positions matter.
  • Suffix array of an integer array. Nothing in doubling needs letters; rank compress the integers first. LeetCode 718 ("Maximum Length of Repeated Subarray") is the LCS application on integer arrays.
  • Dynamic text. Appending to the text breaks the array; online alternatives are the suffix automaton (append in amortised ) and Ukkonen's suffix tree.

Suffix array, hashing, automaton or tree?

NeedSuffix array + LCPHashing + binary searchSuffix automatonSuffix tree
Build simple, SA-IS (Ukkonen), tricky
Memory (32-bit ints)~– bytes~– bytestens of bytes per char10–20 bytes per char in good implementations (Kurtz 1999)
Deterministicyesno (collisions)yesyes
Pattern query hash + lookup if precomputed per length
Sorted / -th substringnaturalawkwardneeds extra DPnatural (DFS order)
Easy to code under pressuremediumeasymediumhard

In contests, the suffix array + LCP + sparse table is the most versatile single tool for "one fixed string, many substring questions". The module overview has the full decision table.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Find the Index of the First Occurrence in a String (LeetCode 28) — Locate a needle in a haystack. Teaches the binary-search block on a suffix array (overkill here, but a perfect first test of your code against str.find).

Hint

Build of the haystack, binary search for the block of suffixes starting with the needle, return the minimum value in the block (or −1).

2. Distinct Substrings (CSES 2105) — Count the different substrings of a string of length up to . Teaches Claim 4.

Solution
def solve(s):
    sa = suffix_array(s)
    n = len(s)
    return n * (n + 1) // 2 - sum(lcp_kasai(s, sa))

abaa → 8 (a, b, ab, ba, aa, aba, baa, abaa). In Python, use the radix version; a naive sort is too slow on long repetitive tests.

3. Repeating Substring (CSES 2106) — Find a longest substring that occurs at least twice, or report that none exists. Teaches .

Solution
def solve(s):
    sa = suffix_array(s)
    lcp = lcp_kasai(s, sa)
    j = max(range(len(s)), key=lambda t: lcp[t])
    return s[sa[j]:sa[j] + lcp[j]] if lcp[j] else "-1"

aabbaabb → aabb. Why adjacent suffixes suffice: any two suffixes share at most what each adjacent pair between them shares.

4. Longest Duplicate Substring (LeetCode 1044) — Same question, . Teaches the deterministic alternative to binary search + rolling hash.

Hint

The same three lines as problem 3. Compare your answer with the hashing solution from the String Hashing lesson on random tests.

5. Number of Substrings (AtCoder Library Practice Contest, task I) — Count distinct substrings for up to . Teaches that construction is needed at this size, and the ACL's suffix_array/lcp_array API (note its LCP convention).

Hint

Same formula as problem 2. ACL's lcp_array has length and compares with ; the formula is unchanged.

6. Who Says a Pun? (AtCoder ABC 141 E) — Longest substring that occurs twice without overlapping, . Teaches the "positions far enough apart" check.

Solution

Binary search on the length . For a fixed , scan the suffix array; consecutive suffixes with form blocks of suffixes sharing an -letter prefix. If some block has , two of its occurrences do not overlap.

def longest_nonoverlap(s):
    n = len(s)
    sa = suffix_array(s); lcp = lcp_kasai(s, sa)
    def ok(L):
        lo = hi = sa[0]
        for j in range(1, n):
            if lcp[j] >= L:
                lo, hi = min(lo, sa[j]), max(hi, sa[j])
                if hi - lo >= L:
                    return True
            else:
                lo = hi = sa[j]
        return False
    a, b = 0, n // 2
    while a < b:
        mid = (a + b + 1) // 2
        a, b = (mid, b) if ok(mid) else (a, mid - 1)
    return a

ababa → 2 (ab at 0 and 2); strangeorange → 5 (range). Monotone: if length works, so does .

7. Pattern Positions (CSES 2104) — For many patterns, print the first position where each occurs. Teaches "minimum over the binary-search block", answered with a sparse table on .

Hint

Block by two binary searches; the answer is (1-based). Build a sparse table over for range minima.

8. Substring Order I (CSES 2108) — The -th smallest distinct substring. Teaches Application 5.

Solution
def kth_distinct(s, k):
    sa = suffix_array(s); lcp = lcp_kasai(s, sa); n = len(s)
    for j in range(n):
        new = n - sa[j] - lcp[j]
        if k <= new:
            return s[sa[j]:sa[j] + lcp[j] + k]
        k -= new

banana, → ba; → anana (see the table above).

9. Substring Order II (CSES 2109) — The -th smallest substring when repeated occurrences count separately. Teaches occurrence counts from LCP blocks.

Hint

For each candidate prefix length of the current suffix, the number of copies is the length of the run of following suffixes with . A cleaner route is a suffix automaton with occurrence counts; with a suffix array, walk lengths and use RMQ/binary search to find each run's end.

10. Match & Catch (Codeforces 427D) — Shortest substring that occurs exactly once in each of two strings. Teaches LCP reasoning across a separator.

Hint

Build the SA of A#B. A substring occurring exactly once in each means: two adjacent suffixes from different strings, whose common prefix length satisfies (no third suffix shares it). The candidate length is if it is .

11. String (Codeforces 123D) — Sum over all distinct substrings of , where is the number of occurrences. Teaches LCP intervals with a monotonic stack.

Hint

Each distinct substring is a pair (LCP interval, length). Process the LCP array with a monotonic stack: when an interval of suffixes with LCP values in closes, it contributes . Leaves (single suffixes) contribute their unshared lengths with .

12. Fake News (hard) (Codeforces 802I) — Sum over all distinct substrings of the square of their occurrence count. Teaches the same stack technique as 11, a common Codeforces pattern.

Hint

Identical structure to problem 11 with in place of . Check both against brute force on strings of length ≤ 8.

Common mistakes & interview follow-ups

"What is a suffix array, in one sentence?" The starting positions of all suffixes, listed in sorted order of the suffixes; with the LCP array it answers most substring questions about a fixed text.

"Build it." Say the naive first, then prefix doubling: ranks by letters, pairs give ranks by , rounds. Mention radix sort for and SA-IS/DC3 for by name.

"Why is Kasai linear if there is a while inside a for?" drops by at most one per suffix (Claim 3) and never exceeds , so total increases are at most .

"Suffix array or suffix tree?" Same power for most problems, 3–5× less memory, simpler code and better cache behaviour for the array; the tree gives queries and online construction. Enhanced suffix arrays close most of the gap.

"Number of distinct substrings — prove the formula." Claim 4: each suffix contributes its prefixes longer than its LCP with the previous suffix.

"How would you search a 3 GB genome for millions of short reads?" FM-index (BWT + rank tables + sampled SA), backward search, as BWA/Bowtie do; mention memory: the plain suffix array of a genome is over 12 GB.

Mistakes interviewers watch for: sorting suffix strings in memory ( space); wrong LCP convention; overflow in ; non-unique separators; forgetting to reset ; claiming doubling is while using sort (that is ).

Quick quiz

1. Write the suffix array and LCP array of abaab.

Answer

Suffixes sorted: aab (2), ab (3), abaab (0), b (4), baab (1). , . Distinct substrings: .

2. In the doubling round with on banana, why does suffix 3 come before suffix 1, although both start an?

Answer

Their pairs are and . Rank 0 belongs to a, rank 1 to an…; ana ends where anana continues, so ana is smaller.

3. Kasai found for suffix 1 of banana. What can you say about the LCP of suffix 2 with its predecessor, before comparing anything?

Answer

It is at least (it is exactly 2: nana vs na).

4. Why must the separator in A + '#' + B be unique?

Answer

Otherwise a common prefix of a suffix in A and a suffix in B could continue through # into the other string, reporting a "common substring" that exists in neither.

5. What is the BWT of abab$? ($ is the smallest character.)

Answer

Sorted rotations: $abab, ab$ab, abab$, b$aba, bab$a. Last column: bb$aa.

Further reading / sources

  • Udi Manber, Gene Myers, "Suffix arrays: a new method for on-line string searches", SIAM Journal on Computing 22(5), 1993, pp. 935–948 (first presented at SODA 1990). Doubling construction and the search.
  • Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, Kunsoo Park, "Linear-time longest-common-prefix computation in suffix arrays and its applications", CPM 2001, LNCS 2089, pp. 181–192.
  • Juha Kärkkäinen, Peter Sanders, "Simple linear work suffix array construction", ICALP 2003, LNCS 2719; with Stefan Burkhardt, Journal of the ACM 53(6), 2006.
  • Ge Nong, Sen Zhang, Wai Hong Chan, "Linear suffix array construction by almost pure induced-sorting", Data Compression Conference 2009, pp. 193–202.
  • Michael Burrows, David Wheeler, "A block-sorting lossless data compression algorithm", DEC SRC Research Report 124, 1994.
  • Paolo Ferragina, Giovanni Manzini, "Opportunistic data structures with applications", FOCS 2000.
  • Mohamed Ibrahim Abouelhoda, Stefan Kurtz, Enno Ohlebusch, "Replacing suffix trees with enhanced suffix arrays", Journal of Discrete Algorithms 2(1), 2004.
  • Heng Li, Richard Durbin, "Fast and accurate short read alignment with Burrows–Wheeler transform", Bioinformatics 25(14), 2009 (BWA). Ben Langmead, Cole Trapnell, Mihai Pop, Steven Salzberg, "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome", Genome Biology 10:R25, 2009 (Bowtie).
  • Gonzalo Navarro, Veli Mäkinen, "Compressed full-text indexes", ACM Computing Surveys 39(1), 2007.
  • Katherine Lee et al., "Deduplicating Training Data Makes Language Models Better", ACL 2022.
  • cp-algorithms: Suffix Array (cyclic-shift doubling with counting sort) and the AtCoder Library string documentation.
  • Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, ch. 7 (applications) and §7.14 (suffix arrays).
  • The worked numbers on this page (the banana ranks per round, Kasai trace, binary-search trace, banana#cabana LCS, -th substring table, BWT, mississippi values, and the timings on an Apple M5) were produced by running the code shown; the visualizer is generated by scripts/traces/suffix_array_doubling.py.

Previous lesson: Aho–Corasick (Multi-Pattern Matching) · Next lesson: Suffix Automaton

Related: String Algorithms overview · String Hashing in Depth · Sparse Tables & Sqrt Decomposition · Non-Comparison Sorts · Binary Search Mastery · Suffix Trees · Course home