Strings

Alphabets and strings over alphabets

1. An alphabet is a finite set and usually denoted [math]\Sigma[/math].
2. The elements of an alphabet [math]\Sigma[/math] are called its characters.
3. A string over alphabet [math]\Sigma[/math] is an ordered sequence of characters of [math]\Sigma[/math].
4. The length of a string [math]str[/math] is the number of characters and denoted by [math]|str|[/math] or [math]\ell (str)[/math].
5. 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].
6. 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
   1. [math]\ell (str1) \le \ell (str2)[/math] and
   2. for [math]i \in \{ 1,...,\ell (str1)\}[/math] it is [math]str1[i] = str2[i][/math].
7. Analogously, we say that [math]str1[/math] is a suffix of [math]str2[/math] if
   1. [math]\ell (str1) \le \ell (str2)[/math] and
   2. for [math]i \in \{ 1,...,\ell (str1)\}[/math] it is [math]str1[i]=str2[\ell (str2)- \ell(str1)+i][/math].
8. 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:

1. [math]str1[/math] is a proper prefix of [math]str2[/math].
2. 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].