Suffix Array Construction

Take any string — say banana. A suffix is the tail starting at some position: banana, anana, nana, ana, na, a. Sort those six suffixes alphabetically and you get a neat ranked list. That ranked list, stored as an array of start positions, is the suffix array (SA).

Why bother? With a suffix array you can binary-search for any pattern in $O(m \log n)$ time ($m$ = pattern length, $n$ = text length), locate all occurrences in seconds, and answer dozens of string questions — longest repeated substring, longest common substring of two texts, compression statistics — in linear time using the companion LCP array (longest common prefix between consecutive suffixes).

The catch is construction. Sorting $n$ suffixes naively costs $O(n^2 \log n)$ comparisons because each comparison can touch up to $n$ characters. For a human genome ($n \approx 3 \times 10^9$) that is completely off the table. The race to reach $O(n)$ time took decades, produced three independent solutions around 2003–2009, and remains one of the cleanest stories in algorithm design.

Type any short word below. The demo builds its suffix array with a clean $O(n \log^2 n)$ prefix-doubling sort (fast enough to follow by eye), then highlights the LCP — how many characters each consecutive pair of sorted suffixes shares.

<p class="hint">Type a word (up to 20 chars). The demo sorts every suffix lexicographically, shows the suffix array (SA) and the longest-common-prefix array (LCP). No suffix tree — pure comparison-based doubling sort.</p>
<div class="input-row">
  <input id="word" type="text" maxlength="20" value="banana" autocomplete="off" spellcheck="false" />
  <button id="run" type="button">Build SA</button>
</div>
<div id="output" class="output"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.input-row { display: flex; gap: .5rem; margin-bottom: .9rem; }
#word { font: 700 16px ui-monospace, monospace; padding: .4rem .6rem;
        border: 1px solid #adb1b8; border-radius: 8px; width: 180px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
.output { overflow-x: auto; }
table { border-collapse: collapse; font-size: .88rem; min-width: 340px; }
th { background: #1d3557; color: #fff; padding: .3rem .7rem; text-align: left; }
td { padding: .28rem .7rem; border-bottom: 1px solid #e2e8f0; }
tr:last-child td { border-bottom: none; }
tr:nth-child(even) td { background: #f4f7fa; }
.sa-idx { font-weight: 700; color: #1d3557; font-family: ui-monospace, monospace; }
.lcp-val { font-family: ui-monospace, monospace; color: #0a7d33; }
.lcp-zero { color: #aaa; }
.suffix-text { font-family: ui-monospace, monospace; }
.suffix-shared { background: #d0f0de; border-radius: 3px; padding: 0 1px; }

// Suffix array via O(n log^2 n) prefix-doubling (Manber & Myers style).
// Each round doubles the key length; we use JavaScript sort (O(n log n)) per round.
// Total: O(n log^2 n) — correct, legible, easy to verify.

function buildSA(s) {
  const n = s.length;
  if (n === 0) return [];

  // Initial rank = char code
  let rank = Array.from(s, c => c.charCodeAt(0));
  let sa = Array.from({length: n}, (_, i) => i);
  let tmp = new Array(n);

  for (let gap = 1; gap < n; gap *= 2) {
    // Comparator: rank by (rank[i], rank[i+gap])
    const r = rank.slice(); // snapshot
    sa.sort((a, b) => {
      if (r[a] !== r[b]) return r[a] - r[b];
      const ra = a + gap < n ? r[a + gap] : -1;
      const rb = b + gap < n ? r[b + gap] : -1;
      return ra - rb;
    });
    // Rebuild ranks
    tmp[sa[0]] = 0;
    for (let i = 1; i < n; i++) {
      const prev = sa[i - 1], cur = sa[i];
      const same = r[prev] === r[cur] &&
        (prev + gap < n ? r[prev + gap] : -1) === (cur + gap < n ? r[cur + gap] : -1);
      tmp[cur] = tmp[prev] + (same ? 0 : 1);
    }
    rank = tmp.slice();
    if (rank[sa[n - 1]] === n - 1) break; // all ranks distinct — done early
  }
  return sa;
}

// Kasai's O(n) LCP array algorithm.
function buildLCP(s, sa) {
  const n = s.length;
  const rank = new Array(n);
  for (let i = 0; i < n; i++) rank[sa[i]] = i;
  const lcp = new Array(n).fill(0);
  let h = 0;
  for (let i = 0; i < n; i++) {
    if (rank[i] > 0) {
      const j = sa[rank[i] - 1];
      while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
      lcp[rank[i]] = h;
      if (h > 0) h--;
    }
  }
  return lcp; // lcp[0] = 0 by convention
}

function render() {
  const raw = document.getElementById('word').value.trim();
  const s = raw || 'banana';
  const n = s.length;
  const sa = buildSA(s);
  const lcp = buildLCP(s, sa);

  let html = '<table><thead><tr><th>#</th><th>SA[i]</th><th>LCP</th><th>Suffix</th></tr></thead><tbody>';

  for (let i = 0; i < n; i++) {
    const start = sa[i];
    const suffix = s.slice(start);
    const lcpVal = lcp[i];

    // Highlight the shared prefix with the previous suffix
    const shared = suffix.slice(0, lcpVal);
    const rest = suffix.slice(lcpVal);
    const suffixHtml = lcpVal > 0
      ? '<span class="suffix-shared">' + shared + '</span>' + rest
      : suffix;

    const lcpClass = lcpVal === 0 ? 'lcp-zero' : 'lcp-val';
    const lcpText = i === 0 ? '<span class="lcp-zero">—</span>' :
      '<span class="' + lcpClass + '">' + lcpVal + '</span>';

    html += '<tr>' +
      '<td class="sa-idx">' + i + '</td>' +
      '<td class="sa-idx">' + start + '</td>' +
      '<td>' + lcpText + '</td>' +
      '<td class="suffix-text">' + suffixHtml + '</td>' +
      '</tr>';
  }
  html += '</tbody></table>';
  document.getElementById('output').innerHTML = html;

  // Log for verification
  console.log('SA:', sa.join(','), '| LCP:', lcp.join(','));
}

document.getElementById('run').addEventListener('click', render);
document.getElementById('word').addEventListener('keydown', e => { if (e.key === 'Enter') render(); });
render();

<p class="hint">Type a word (up to 20 chars). The demo sorts every suffix lexicographically, shows the suffix array (SA) and the longest-common-prefix array (LCP). No suffix tree — pure comparison-based doubling sort.</p>
<div class="input-row">
  <input id="word" type="text" maxlength="20" value="banana" autocomplete="off" spellcheck="false" />
  <button id="run" type="button">Build SA</button>
</div>
<div id="output" class="output"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.input-row { display: flex; gap: .5rem; margin-bottom: .9rem; }
#word { font: 700 16px ui-monospace, monospace; padding: .4rem .6rem;
        border: 1px solid #adb1b8; border-radius: 8px; width: 180px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
.output { overflow-x: auto; }
table { border-collapse: collapse; font-size: .88rem; min-width: 340px; }
th { background: #1d3557; color: #fff; padding: .3rem .7rem; text-align: left; }
td { padding: .28rem .7rem; border-bottom: 1px solid #e2e8f0; }
tr:last-child td { border-bottom: none; }
tr:nth-child(even) td { background: #f4f7fa; }
.sa-idx { font-weight: 700; color: #1d3557; font-family: ui-monospace, monospace; }
.lcp-val { font-family: ui-monospace, monospace; color: #0a7d33; }
.lcp-zero { color: #aaa; }
.suffix-text { font-family: ui-monospace, monospace; }
.suffix-shared { background: #d0f0de; border-radius: 3px; padding: 0 1px; }

// Suffix array via O(n log^2 n) prefix-doubling (Manber & Myers style).
// Each round doubles the key length; we use JavaScript sort (O(n log n)) per round.
// Total: O(n log^2 n) — correct, legible, easy to verify.

function buildSA(s) {
  const n = s.length;
  if (n === 0) return [];

  // Initial rank = char code
  let rank = Array.from(s, c => c.charCodeAt(0));
  let sa = Array.from({length: n}, (_, i) => i);
  let tmp = new Array(n);

  for (let gap = 1; gap < n; gap *= 2) {
    // Comparator: rank by (rank[i], rank[i+gap])
    const r = rank.slice(); // snapshot
    sa.sort((a, b) => {
      if (r[a] !== r[b]) return r[a] - r[b];
      const ra = a + gap < n ? r[a + gap] : -1;
      const rb = b + gap < n ? r[b + gap] : -1;
      return ra - rb;
    });
    // Rebuild ranks
    tmp[sa[0]] = 0;
    for (let i = 1; i < n; i++) {
      const prev = sa[i - 1], cur = sa[i];
      const same = r[prev] === r[cur] &&
        (prev + gap < n ? r[prev + gap] : -1) === (cur + gap < n ? r[cur + gap] : -1);
      tmp[cur] = tmp[prev] + (same ? 0 : 1);
    }
    rank = tmp.slice();
    if (rank[sa[n - 1]] === n - 1) break; // all ranks distinct — done early
  }
  return sa;
}

// Kasai's O(n) LCP array algorithm.
function buildLCP(s, sa) {
  const n = s.length;
  const rank = new Array(n);
  for (let i = 0; i < n; i++) rank[sa[i]] = i;
  const lcp = new Array(n).fill(0);
  let h = 0;
  for (let i = 0; i < n; i++) {
    if (rank[i] > 0) {
      const j = sa[rank[i] - 1];
      while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++;
      lcp[rank[i]] = h;
      if (h > 0) h--;
    }
  }
  return lcp; // lcp[0] = 0 by convention
}

function render() {
  const raw = document.getElementById('word').value.trim();
  const s = raw || 'banana';
  const n = s.length;
  const sa = buildSA(s);
  const lcp = buildLCP(s, sa);

  let html = '<table><thead><tr><th>#</th><th>SA[i]</th><th>LCP</th><th>Suffix</th></tr></thead><tbody>';

  for (let i = 0; i < n; i++) {
    const start = sa[i];
    const suffix = s.slice(start);
    const lcpVal = lcp[i];

    // Highlight the shared prefix with the previous suffix
    const shared = suffix.slice(0, lcpVal);
    const rest = suffix.slice(lcpVal);
    const suffixHtml = lcpVal > 0
      ? '<span class="suffix-shared">' + shared + '</span>' + rest
      : suffix;

    const lcpClass = lcpVal === 0 ? 'lcp-zero' : 'lcp-val';
    const lcpText = i === 0 ? '<span class="lcp-zero">—</span>' :
      '<span class="' + lcpClass + '">' + lcpVal + '</span>';

    html += '<tr>' +
      '<td class="sa-idx">' + i + '</td>' +
      '<td class="sa-idx">' + start + '</td>' +
      '<td>' + lcpText + '</td>' +
      '<td class="suffix-text">' + suffixHtml + '</td>' +
      '</tr>';
  }
  html += '</tbody></table>';
  document.getElementById('output').innerHTML = html;

  // Log for verification
  console.log('SA:', sa.join(','), '| LCP:', lcp.join(','));
}

document.getElementById('run').addEventListener('click', render);
document.getElementById('word').addEventListener('keydown', e => { if (e.key === 'Enter') render(); });
render();

Notice how the LCP values cluster near long repeated substrings. The sum of all LCP values equals the total number of shared prefix characters across consecutive sorted suffixes — a quantity that drives compression and the pattern matching algorithms built on suffix arrays.

The complexity story has four clean chapters:

• Naïve sort — $O(n^2 \log n)$. Sort $n$ suffixes with a comparison sort; each comparison costs up to $O(n)$ character reads. Unusable beyond a few thousand characters.
• Prefix doubling — $O(n \log^2 n)$. Manber & Myers (1993) observed that once you rank suffixes by their first $2^k$ characters, you can rank them by their first $2^{k+1}$ characters in $O(n \log n)$ work per doubling. Total cost: $O(\log n)$ rounds at $O(n \log n)$ each. An elegant bridge but still super-linear.
• DC3 / Skew — $O(n)$. Kärkkäinen & Sanders (2003) proved the first linear bound. Their skew algorithm splits positions into those whose index is divisible by 3 and those that are not, recursively sorts the 2/3-sample, then merges. A graduate-student masterpiece.
• SA-IS — $O(n)$. Nong, Zhang & Chan (2009) gave a cleaner linear algorithm based on induced sorting: classify each suffix as S-type or L-type, identify a small set of LMS (leftmost S) suffixes, sort them recursively, then induce the order of all other suffixes in two linear scans. SA-IS uses less memory than DC3 and handles integer alphabets directly.

The lower bound in the comparison model is $\Omega(n \log n)$ (you need to sort), but over integer alphabets of size $\sigma \leq n$ the $O(n)$ algorithms are tight. This is a solved, proven result — not open, not a Millennium Prize — but the journey from naïve to linear is a showcase of algorithmic technique that sits alongside sorting lower bounds and pattern matching in every advanced algorithms course.

Suffix arrays are the invisible skeleton of several industries:

• Genome assembly and alignment: tools like BWA and Bowtie index a reference genome with a suffix array (augmented with the Burrows-Wheeler Transform) to align millions of short reads per second. Without linear-time construction the human genome index would take days to build.
• Full-text search engines: Apache Lucene and similar systems use inverted indices, but suffix arrays handle richer queries (substring search, approximate match) that inverted indices cannot.
• Data compression: the Burrows-Wheeler Transform (BWT) reorders a text so similar characters cluster, enabling gzip-beating compression (bzip2, LZMA). The BWT is computed almost instantly once you have the suffix array.
• Plagiarism and duplicate detection: the longest common substring of two documents is found in $O(n+m)$ time by merging their suffix arrays and scanning LCP values.
• Bioinformatics beyond DNA: protein sequence search (BLAST-like tools) and RNA structure prediction both lean on suffix-array techniques.

The pattern here is the same as with pattern matching: invest $O(n)$ in preprocessing, then answer any query in near-constant time.

A suffix array is just a sorted list of string tails. But building that list in linear time — without the overhead of a suffix tree — required two decades of algorithmic creativity, from Manber & Myers's prefix doubling to Kärkkäinen & Sanders's skew trick to Nong, Zhang & Chan's induced-sorting tour de force.

The result is proven optimal over integer alphabets: $O(n)$ time, $O(n)$ space, no hidden constants worth worrying about. It is not an open problem or a Millennium Prize — it is a closed chapter, celebrated precisely because the path from $O(n^2 \log n)$ to $O(n)$ is so instructive.

Every time a genome sequencer aligns a read in milliseconds, or bzip2 shrinks a file by 70 %, or a search engine finds every occurrence of a phrase in a billion-word corpus, a suffix array built in linear time is doing the work. That is what it looks like when an algorithm is not just correct but beautifully, provably efficient.