Sufunctions

Sufunctions are a class of operations on strings used in formal language theory and string processing. In its common form, a sufunction extracts a suffix of a given string, and a family of sufunctions can be indexed by a starting position.

Definition and variants: Let A be an alphabet and s ∈ A*. For each i with 0 ≤ i ≤ |s|, define suf_i(s) = s[i:]. The set of all suf_i(s) for i in 0..|s| is the suffix family of s. A related notion is suf(s) = { s[i:] | 0 ≤ i ≤ |s| }, the set of all suffixes of s. If a sufunction is defined as mapping s to its i-th suffix, then it is a total function from strings to strings defined by the index i.

Examples: for s = banana, suf_0(s) = banana, suf_3(s) = ana, suf_5(s) = a.

Computation and properties: all suffixes can be produced in linear time from the end of s, and in many implementations suf_i can be represented as a view or slice without copying. Sufunctions relate to prefix-based notions such as the prefix function and the Z-function, offering a suffix-oriented counterpart for pattern analysis and indexing.

Applications: suffix-based indexing and search using suffix arrays and suffix trees, data compression, and bioinformatics for suffix-level pattern matching and alignments. Sufunctions provide a convenient formalism for describing operations that depend on the trailing portion of strings and for building suffix-aware data structures. See also: suffix array, suffix tree, prefix function, Z-function, substring.