Suffix array

Example string: abac

// Has 5 suffixes:
abac$  // position 1
bac$   // position 2
ac$    // position 3
c$     // position 4
$      // position 5

Sort them lexographically

$      // position 5
abac$  // position 1
ac$    // position 3
bac$   // position 2
c$     // position 4

Suffix array

5,1,3,2,4
  • Exact string matching: Find all suffixes which begin with pattern P ⇒ Find suffixes with smallest and largest lexicographical value (results lie in this block)
  • Suffix tree construction