Strings

Alphabets and strings over alphabets

1. An alphabet is a finite set and usually denoted [math]\displaystyle{ \Sigma }[/math].
2. The elements of an alphabet [math]\displaystyle{ \Sigma }[/math] are called its characters.
3. A string over alphabet [math]\displaystyle{ \Sigma }[/math] is an ordered sequence of characters of [math]\displaystyle{ \Sigma }[/math].
4. The length of a string [math]\displaystyle{ str }[/math] is the number of characters and denoted by [math]\displaystyle{ |str| }[/math] or [math]\displaystyle{ \ell (str) }[/math].
5. For [math]\displaystyle{ i\in \{ 1,...,\ell (str)\} }[/math], the character of [math]\displaystyle{ str }[/math] at position [math]\displaystyle{ i }[/math] is denoted by [math]\displaystyle{ str[i] }[/math].
6. For two strings [math]\displaystyle{ str1 }[/math] and [math]\displaystyle{ str2 }[/math] over some alphabet [math]\displaystyle{ \Sigma }[/math], we say that [math]\displaystyle{ str1 }[/math] is a prefix of [math]\displaystyle{ str2 }[/math] if
   1. [math]\displaystyle{ \ell (str1) \le \ell (str2) }[/math] and
   2. for [math]\displaystyle{ i \in \{ 1,...,\ell (str1)\} }[/math] it is [math]\displaystyle{ str1[i] = str2[i] }[/math].
7. Analogously, we say that [math]\displaystyle{ str1 }[/math] is a suffix of [math]\displaystyle{ str2 }[/math] if
   1. [math]\displaystyle{ \ell (str1) \le \ell (str2) }[/math] and
   2. for [math]\displaystyle{ i \in \{ 1,...,\ell (str1)\} }[/math] it is [math]\displaystyle{ str1[i]=str2[\ell (str2)- \ell(str1)+i] }[/math].
8. We say that [math]\displaystyle{ str1 }[/math] is a proper prefix (resp., suffix) of [math]\displaystyle{ str2 }[/math] if [math]\displaystyle{ str1 }[/math] is a prefix (resp., suffix) of [math]\displaystyle{ str2 }[/math] and [math]\displaystyle{ \ell (str1) \lt \ell (str2) }[/math].

Lexicographic order

Suppose a comparison is defined on alphabet [math]\displaystyle{ \Sigma }[/math]. For two strings [math]\displaystyle{ str1 }[/math] and [math]\displaystyle{ str2 }[/math] over [math]\displaystyle{ \Sigma }[/math], we say that [math]\displaystyle{ str1 }[/math] is lexicographically smaller than [math]\displaystyle{ str2 }[/math] - or alternatively, [math]\displaystyle{ str1 }[/math] precedes [math]\displaystyle{ str2 }[/math] lexicographically - if [math]\displaystyle{ str1 \neq str2 }[/math] and one of the following two conditions is fulfilled:

1. [math]\displaystyle{ str1 }[/math] is a proper prefix of [math]\displaystyle{ str2 }[/math].
2. Let [math]\displaystyle{ \ell := \min \{ \ell (str1), \ell (str2)\} }[/math] for short. Let [math]\displaystyle{ k := \min \{i \mid i \in \{1,...,\ell \} , str1[i] \neq str2[i] \} }[/math]. Now the second condition is [math]\displaystyle{ str1[k] \lt str2[k] }[/math].

If [math]\displaystyle{ str1 }[/math] precedes [math]\displaystyle{ str2 }[/math] we write [math]\displaystyle{ str1 \prec str2 }[/math], and we write [math]\displaystyle{ str1 \preceq str2 }[/math] if either [math]\displaystyle{ str1 }[/math] precedes [math]\displaystyle{ str2 }[/math] or [math]\displaystyle{ str1 = str2 }[/math].