ABSTRACT

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 suf f i = s[i]s[i + 1]…s[|s|] be the suffix of s starting at ith position.