LCP Array

Use inverse suffix ranks and Kasai reuse to compute adjacent longest common prefixes in linear time.

Core idea

Kasai's algorithm visits suffixes in text order. If one suffix shares h characters with its suffix-array predecessor, the next text suffix can reuse at least h minus one before extending comparisons.

Read the visualization

The suffix-array rank selects the comparison neighbor. A highlighted prefix shows reused characters, then grows only while new characters match.

LCP of adjacent suffixes (Kasai)

StartSuffixrankLCP↑

5a0-

3ana1

1anana2

0banana3

4na4

2nana5

Build inverse suffix ranks and initialize the reusable prefix length to zero.

1function kasai(s: string, sa: number[]): number[] {
const n = s.length;
const rank = new Array(n);
for (let i = 0; i < n; i++) rank[sa[i]] = i; // sa init
const lcp = new Array(n).fill(0);
let h = 0;
for (let i = 0; i < n; i++) {          // init index  i init
  if (rank[i] > 0) {
    const j = sa[rank[i] - 1];         // fill predecessor  suffix 
    while (i + h < n && j + h < n && s[i + h] === s[j + h]) h++; // h fill
    lcp[rank[i]] = h;                  // fill LCP
    if (h > 0) h--;                    // fill character: h fill 1
  } else {
    h = 0;                             // rank 0: skip predecessor 
  }
}
return lcp;
18}

original stringbanana

sa[5,3,1,0,4,2]

current suffix i-

1 / 8

Complexity and tradeoffs

Time: O(n). Space: O(n). The reused prefix length decreases by at most one per text position, bounding total comparisons.

Invariant: The carried match length is a valid lower bound for the next suffix comparison and decreases by at most one between text positions.

Where it fits

Together with a suffix array, LCP values reveal repeated substrings and support range-minimum queries for arbitrary suffix-prefix lengths.

Algorithm Visualizer

LCP Array

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits