Suffix Trees and Suffix Arrays

Suffix trees and suffix arrays are versatile data structures fundamental to string processing applications. Let s′ denote a string over the alphabet Σ. Let $ /∈ Σ be a unique termination character, and s = s′$ be the string resulting from appending $ to s′. We use the following notation: |s| denotes the size of s, s[i] denotes the ith character of s, and s[i..j] denotes the substring s[i]s[i + 1] . . . s[j]. Let suffi = s[i]s[i + 1] . . . s[|s|] be the suffix of s starting at ith position.