↩ back to Exact Match

Suffix Array

Every exact-match entry on this site so far answers one question: given this pattern and this text, find every match, right now — KMP, the Z-algorithm, Rabin-Karp, Boyer-Moore and its Horspool variant, and Aho-Corasick all pay their cost per search, scanning the text (or a whole known pattern set) fresh each time. A suffix array flips the question around: preprocess the text once, before any pattern is known, into a sorted list of every one of its suffixes — then answer any future pattern, one nobody knew about at indexing time, with two binary searches instead of a scan. It's the right tool when the text is fixed and long-lived and queries keep arriving — a genome, a codebase, a fixed document — not for a single one-off search, where the preprocessing itself costs more than just scanning once would.

Try it

Enter a text (lowercase letters only, up to 16 characters) and press Build to sort all of its suffixes — the table below shows each suffix's start index and the suffix itself, in the sorted order the search below relies on. Then enter a pattern and step through the search: one binary search proves the pattern occurs by landing on any one matching suffix, then — with expand to find every match checked — the demo walks outward from that suffix through its immediate neighbors in the sorted table, since every suffix starting with the pattern sits in one unbroken block. Uncheck the box to see what happens if that expansion is skipped.

Why it works

The suffix array of a text of length n is just a permutation of 0..n-1 — the starting indices of all n suffixes, listed in the lexicographic order of the suffixes themselves rather than of their positions. That one sort does all the work: because lexicographic order agrees with "starts with" on any fixed-length prefix, if two suffixes in the sorted array both start with a pattern P, then every suffix sorted between them must also start with P — nothing else could sit between them without either starting with P too or disagreeing with the ordering. So every occurrence of P in the text corresponds to one unbroken block in the sorted array, never a scattered set of positions.

That's what makes binary search work here at all: instead of searching for an exact value, each step in the search below compares P against just the first |P| characters of the suffix at the midpoint, and rules out half the remaining suffixes per comparison, exactly like an ordinary binary search over a sorted array. Landing on any one match is proof the pattern occurs — and because the rest of its occurrences are guaranteed to be that suffix's immediate neighbors in the array, finding all of them is just a matter of checking outward, left and right, until a neighbor's prefix stops matching. That walk costs work proportional to the number of matches actually found, not to the size of the whole array.

Reference implementation

This is the exact scheme the demo above steps through:

function buildSuffixArray(text) {
  const n = text.length;
  const sa = Array.from({ length: n }, (_, i) => i);
  sa.sort((a, b) => {
    const sa_ = text.slice(a), sb_ = text.slice(b);
    if (sa_ < sb_) return -1;
    if (sa_ > sb_) return 1;
    return 0;
  });
  return sa;
}

function search(text, sa, pat) {
  // binary search for any one suffix that starts with pat
  let lo = 0, hi = sa.length - 1, found = -1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    const prefix = text.slice(sa[mid], sa[mid] + pat.length);
    if (prefix === pat) { found = mid; break; }
    else if (prefix < pat) lo = mid + 1;
    else hi = mid - 1;
  }
  if (found === -1) return [];

  // matches with a shared prefix sort contiguously -- expand outward from `found`
  let left = found, right = found;
  while (left > 0 && text.slice(sa[left - 1], sa[left - 1] + pat.length) === pat) left--;
  while (right < sa.length - 1 && text.slice(sa[right + 1], sa[right + 1] + pat.length) === pat) right++;

  return sa.slice(left, right + 1).sort((a, b) => a - b);
}

Pitfalls

Finding one matching suffix is proof the pattern occurs — it is not proof of where all of it occurs. On this page's own default example, "mississippi" searched for "is": the binary search needs exactly 2 comparisons to land on rank 2 in the sorted table — the suffix "issippi", starting at text position 4 — and stopping right there, which is what the "expand" checkbox above does when unchecked, reports that single position as the answer. But "is" genuinely occurs twice in "mississippi" (m-iss-iss-ippi, positions 1 and 4), and the second occurrence is silently missing. Expanding outward from rank 2 finds it in three more comparisons: checking rank 1 ("ippi", prefix "ip" — fails, stop on the left) and rank 3 ("ississippi", prefix "is" — matches, keep going right), then rank 4 ("mississippi", prefix "mi" — fails, stop). Checked, not just claimed: against 20,000 random (text, pattern) pairs compared to a brute-force scan, the find-then-expand approach matched brute force exactly every time, and skipping the expansion step reproduces this exact single-match undercount on every pair with more than one real occurrence.

The naive sort shipped above is a real, measured O(n²) trap on repetitive text — not just an asymptotic worry. Comparing two suffixes by slicing and comparing full strings costs up to O(n) character checks per comparison when the suffixes share a long common prefix, and a comparison-based sort makes O(n log n) of them. Counting the actual character comparisons a real sort performs (not wall-clock time, which modern engines optimize well enough on either input to hide the effect) makes the gap concrete: on a string of n repeated as versus a random string of the same length, the repeated-character work per comparison grows with n itself, and the ratio of total character comparisons to n exactly doubles every time n doubles — 100.5×, 200.5×, 400.5× at n = 200, 400, 800 — the signature of quadratic growth, against a random string's much flatter 11.2×, 14.0×, 17.3× over the same sizes. At n = 800 that's 320,399 character comparisons on repeated text against 13,845 on random text of the same length. Real suffix array construction algorithms — prefix doubling (O(n log n)) and SA-IS (O(n)) — fix this by comparing suffixes indirectly through rank tables built up over several passes, instead of re-scanning characters on every comparison; neither is implemented on this page, which uses the naive sort above for clarity.

Complexity

Time: as shipped, construction is a comparator-based sort — O(n log n) comparisons, each up to O(n) character work in the worst case, giving O(n² log n) worst-case time overall (measured directly above, not just asserted). Each query after that is cheap: one binary search of O(log n) steps, each comparing up to |pattern| characters, to prove a match exists — O(m log n) — plus O(m·k) more to read off all k matches by expanding outward, cost proportional to the output rather than to n. That per-query cost holds for as many patterns as are asked, all against the one array built once. Space: O(n) — the array stores n integer start indices into the original text, not n copies of increasingly short substrings; the O(n²) figure sometimes quoted for "all suffixes of a string" is the total length if every suffix were fully materialized as its own string, which is not what this structure actually keeps.

The other five exact match entries that aren't a Suffix Tree all pay their search cost against the text fresh, every time a pattern is checked. This page inverts that: the one-time sort above is the only cost paid against the text itself, so it's a poor fit for a single one-shot search and the natural choice once the same text is going to be queried repeatedly. Suffix Tree makes the identical trade but changes the mechanism: an edge-compressed trie instead of a sorted array, trading a heavier structure and a slower unconditional build for a query that never pays this page's O(log n) factor. See Choosing an Exact-Match String Matcher for the full comparison across all ten.