# Strings

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Alphabets and strings over alphabets

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

## Lexicographic order

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

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

If $str1$ precedes $str2$ we write $str1 \prec str2$, and we write $str1 \preceq str2$ if either $str1$ precedes $str2$ or $str1 = str2$.