Basic definitions

A string of length n is an array of characters S[1..n]

-- S is a generic string, P is a pattern string, and T is a text string

The length of the string is denoted |S|

A substring S[i..j] is a contiguous subarray

-- The substring is empty if j > i

-- The character at position i, S[i..i] is denoted S(i)

A prefix is a substring S[1..j] that begins at position 1

A suffix is a substring that ends at position |S|

A proper prefix or suffix is one that is neither the whole string nor the empty string