Strings
Alphabets and strings over alphabets
- An alphabet is a finite set and usually denoted [math]\Sigma[/math].
- The elements of an alphabet [math]\Sigma[/math] are called its characters.
- A string over alphabet [math]\Sigma[/math] is an ordered sequence of characters of [math]\Sigma[/math].
- The length of a string [math]str[/math] is the number of characters and denoted by [math]|str|[/math] or [math]\ell (str)[/math].
- For [math]i\in \{ 1,...,\ell (str)\}[/math], the character of [math]str[/math] at position [math]i[/math] is denoted by [math]str[i][/math].
- For two strings [math]str1[/math] and [math]str2[/math] over some alphabet [math]\Sigma[/math], we say that [math]str1[/math] is a prefix of [math]str2[/math] if
- [math]\ell (str1) \le \ell (str2)[/math] and
- for [math]i \in \{ 1,...,\ell (str1)\}[/math] it is [math]str1[i] = str2[i][/math].
- Analogously, we say that [math]str1[/math] is a suffix of [math]str2[/math] if
- [math]\ell (str1) \le \ell (str2)[/math] and
- for [math]i \in \{ 1,...,\ell (str1)\}[/math] it is [math]str1[i]=str2[\ell (str2)- \ell(str1)+i][/math].
- We say that [math]str1[/math] is a proper prefix (resp., suffix) of [math]str2[/math] if [math]str1[/math] is a prefix (resp., suffix) of [math]str2[/math] and [math]\ell (str1) \lt \ell (str2)[/math].
Lexicographic order
Suppose a comparison is defined on alphabet [math]\Sigma[/math]. For two strings [math]str1[/math] and [math]str2[/math] over [math]\Sigma[/math], we say that [math]str1[/math] is lexicographically smaller than [math]str2[/math] - or alternatively, [math]str1[/math] precedes [math]str2[/math] lexicographically - if [math]str1 \neq str2[/math] and one of the following two conditions is fulfilled:
- [math]str1[/math] is a proper prefix of [math]str2[/math].
- Let [math]\ell := \min \{ \ell (str1), \ell (str2)\}[/math] for short. Let [math]k := \min \{i \mid i \in \{1,...,\ell \} , str1[i] \neq str2[i] \}[/math]. Now the second condition is [math]str1[k] \lt str2[k][/math].
If [math]str1[/math] precedes [math]str2[/math] we write [math]str1 \prec str2[/math], and we write [math]str1 \preceq str2[/math] if either [math]str1[/math] precedes [math]str2[/math] or [math]str1 = str2[/math].