String Algorithms

A substring is a contiguous sequence of characters taken from s, i.e. s[i..j] for some 0 ≤ i ≤ j < n. Contiguity distinguishes a substring from a subsequence, which need not be contiguous.

There are n − L + 1 starting positions (for 0 ≤ L ≤ n), so a string has Θ(n²) substrings counted by position, though the number of distinct substring values may be smaller.

A prefix is a substring starting at index 0, s[0..k]. A suffix is a substring ending at the last index, s[k..n-1]. Each is a special contiguous substring anchored to one end.

A proper prefix is a prefix that is not the whole string (length < n); likewise a proper suffix is shorter than s. The empty string and all shorter prefixes are proper; s itself is not.

A palindrome is a string that reads the same forwards and backwards, i.e. s[i] = s[n-1-i] for all i. Examples: 'aba', 'abba'. Palindromes may have odd or even length.

A border is a proper prefix that is also a (proper) suffix of the string. For 'abacaba' the borders are 'a' and 'aba'. The longest proper border is central to KMP.