https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Strings&feed=atom&action=historyStrings - Revision history2024-03-28T09:50:24ZRevision history for this page on the wikiMediaWiki 1.38.4https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Strings&diff=3016&oldid=prevWeihe: /* Definitions */2015-05-17T11:39:46Z<p><span dir="auto"><span class="autocomment">Definitions</span></span></p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 11:39, 17 May 2015</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Checkup]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Checkup]]</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Background]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Background]]</div></td></tr>
<tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>==<del style="font-weight: bold; text-decoration: none;">Definitions</del>==</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>==<ins style="font-weight: bold; text-decoration: none;">Alphabets and strings over alphabets</ins>==</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div># An '''alphabet''' is a finite set and usually denoted <math>\Sigma</math>.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div># An '''alphabet''' is a finite set and usually denoted <math>\Sigma</math>.</div></td></tr>
<tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div># The elements of an alphabet <math>\Sigma</math> are called its '''characters'''.</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div># The elements of an alphabet <math>\Sigma</math> are called its '''characters'''.</div></td></tr>
</table>Weihehttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Strings&diff=585&oldid=prevCuozzo: 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>\..."2014-10-02T13:35:28Z<p>Created page with "<a href="/index.php?title=Category:Checkup&action=edit&redlink=1" class="new" title="Category:Checkup (page does not exist)">Category:Checkup</a> <a href="/index.php?title=Category:Background&action=edit&redlink=1" class="new" title="Category:Background (page does not exist)">Category:Background</a> ==Definitions== # An '''alphabet''' is a finite set and usually denoted <math>\Sigma</math>. # The elements of an alphabet <math>\..."</p>
<p><b>New page</b></p><div>[[Category:Checkup]]<br />
[[Category:Background]]<br />
==Definitions==<br />
# An '''alphabet''' is a finite set and usually denoted <math>\Sigma</math>.<br />
# The elements of an alphabet <math>\Sigma</math> are called its '''characters'''.<br />
# A '''string''' over alphabet <math>\Sigma</math> is an [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] of characters of <math>\Sigma</math>.<br />
# The '''length''' of a string <math>str</math> is the number of characters and denoted by <math>|str|</math> or <math>\ell (str)</math>.<br />
# 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>.<br />
# 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<br />
## <math>\ell (str1) \le \ell (str2)</math> and<br />
## for <math>i \in \{ 1,...,\ell (str1)\}</math> it is <math>str1[i] = str2[i]</math>.<br />
# Analogously, we say that <math>str1</math> is a '''suffix''' of <math>str2</math> if<br />
## <math>\ell (str1) \le \ell (str2)</math> and<br />
## for <math>i \in \{ 1,...,\ell (str1)\}</math> it is <math>str1[i]=str2[\ell (str2)- \ell(str1)+i]</math>.<br />
#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) < \ell (str2)</math>.<br />
<br />
==Lexicographic order==<br />
Suppose a [[Genericity#Comparison|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:<br />
# <math>str1</math> is a proper prefix of <math>str2</math>.<br />
# 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] < str2[k]</math>.<br />
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>.</div>Cuozzo