# Strings

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

## Alphabets and strings over alphabets

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

## Lexicographic order

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

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

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