Strings: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(Created page with "Category:Checkup Category:Background ==Definitions== # An '''alphabet''' is a finite set and usually denoted <math>\Sigma</math>. # The elements of an alphabet <math>\...")
 
 
Line 1: Line 1:
[[Category:Checkup]]
[[Category:Checkup]]
[[Category:Background]]
[[Category:Background]]
==Definitions==
==Alphabets and strings over alphabets==
# An '''alphabet''' is a finite set and usually denoted <math>\Sigma</math>.
# An '''alphabet''' is a finite set and usually denoted <math>\Sigma</math>.
# The elements of an alphabet <math>\Sigma</math> are called its '''characters'''.
# The elements of an alphabet <math>\Sigma</math> are called its '''characters'''.

Latest revision as of 11:39, 17 May 2015

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].