https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Strings&feed=atom&action=history Strings - Revision history 2024-03-28T09:50:24Z Revision history for this page on the wiki MediaWiki 1.38.4 https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Strings&diff=3016&oldid=prev Weihe: /* 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 &lt;math&gt;\Sigma&lt;/math&gt;.</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 &lt;math&gt;\Sigma&lt;/math&gt;.</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 &lt;math&gt;\Sigma&lt;/math&gt; 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 &lt;math&gt;\Sigma&lt;/math&gt; are called its '''characters'''.</div></td></tr> </table> Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Strings&diff=585&oldid=prev Cuozzo: 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 &quot;<a href="/index.php?title=Category:Checkup&amp;action=edit&amp;redlink=1" class="new" title="Category:Checkup (page does not exist)">Category:Checkup</a> <a href="/index.php?title=Category:Background&amp;action=edit&amp;redlink=1" class="new" title="Category:Background (page does not exist)">Category:Background</a> ==Definitions== # An &#039;&#039;&#039;alphabet&#039;&#039;&#039; is a finite set and usually denoted &lt;math&gt;\Sigma&lt;/math&gt;. # The elements of an alphabet &lt;math&gt;\...&quot;</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 &lt;math&gt;\Sigma&lt;/math&gt;.<br /> # The elements of an alphabet &lt;math&gt;\Sigma&lt;/math&gt; are called its '''characters'''.<br /> # A '''string''' over alphabet &lt;math&gt;\Sigma&lt;/math&gt; is an [[Sets and sequences#Ordered and sorted sequences|ordered sequence]] of characters of &lt;math&gt;\Sigma&lt;/math&gt;.<br /> # The '''length''' of a string &lt;math&gt;str&lt;/math&gt; is the number of characters and denoted by &lt;math&gt;|str|&lt;/math&gt; or &lt;math&gt;\ell (str)&lt;/math&gt;.<br /> # For &lt;math&gt;i\in \{ 1,...,\ell (str)\}&lt;/math&gt;, the character of &lt;math&gt;str&lt;/math&gt; at position &lt;math&gt;i&lt;/math&gt; is denoted by &lt;math&gt;str[i]&lt;/math&gt;.<br /> # For two strings &lt;math&gt;str1&lt;/math&gt; and &lt;math&gt;str2&lt;/math&gt; over some alphabet &lt;math&gt;\Sigma&lt;/math&gt;, we say that &lt;math&gt;str1&lt;/math&gt; is a '''prefix''' of &lt;math&gt;str2&lt;/math&gt; if<br /> ## &lt;math&gt;\ell (str1) \le \ell (str2)&lt;/math&gt; and<br /> ## for &lt;math&gt;i \in \{ 1,...,\ell (str1)\}&lt;/math&gt; it is &lt;math&gt;str1[i] = str2[i]&lt;/math&gt;.<br /> # Analogously, we say that &lt;math&gt;str1&lt;/math&gt; is a '''suffix''' of &lt;math&gt;str2&lt;/math&gt; if<br /> ## &lt;math&gt;\ell (str1) \le \ell (str2)&lt;/math&gt; and<br /> ## for &lt;math&gt;i \in \{ 1,...,\ell (str1)\}&lt;/math&gt; it is &lt;math&gt;str1[i]=str2[\ell (str2)- \ell(str1)+i]&lt;/math&gt;.<br /> #We say that &lt;math&gt;str1&lt;/math&gt; is a '''proper''' prefix (resp., suffix) of &lt;math&gt;str2&lt;/math&gt; if &lt;math&gt;str1&lt;/math&gt; is a prefix (resp., suffix) of &lt;math&gt;str2&lt;/math&gt; and &lt;math&gt;\ell (str1) &lt; \ell (str2)&lt;/math&gt;.<br /> <br /> ==Lexicographic order==<br /> Suppose a [[Genericity#Comparison|comparison]] is defined on alphabet &lt;math&gt;\Sigma&lt;/math&gt;. For two strings &lt;math&gt;str1&lt;/math&gt; and &lt;math&gt;str2&lt;/math&gt; over &lt;math&gt;\Sigma&lt;/math&gt;, we say that &lt;math&gt;str1&lt;/math&gt; is '''lexicographically''' smaller than &lt;math&gt;str2&lt;/math&gt; - or alternatively, &lt;math&gt;str1&lt;/math&gt; '''precedes''' &lt;math&gt;str2&lt;/math&gt; '''lexicographically''' - if &lt;math&gt;str1 \neq str2&lt;/math&gt; and one of the following two conditions is fulfilled:<br /> # &lt;math&gt;str1&lt;/math&gt; is a proper prefix of &lt;math&gt;str2&lt;/math&gt;.<br /> # Let &lt;math&gt;\ell := \min \{ \ell (str1), \ell (str2)\}&lt;/math&gt; for short. Let &lt;math&gt;k := \min \{i \mid i \in \{1,...,\ell \} , str1[i] \neq str2[i] \}&lt;/math&gt;. Now the second condition is &lt;math&gt;str1[k] &lt; str2[k]&lt;/math&gt;.<br /> If &lt;math&gt;str1&lt;/math&gt; precedes &lt;math&gt;str2&lt;/math&gt; we write &lt;math&gt;str1 \prec str2&lt;/math&gt;, and we write &lt;math&gt;str1 \preceq str2&lt;/math&gt; if either &lt;math&gt;str1&lt;/math&gt; precedes &lt;math&gt;str2&lt;/math&gt; or &lt;math&gt;str1 = str2&lt;/math&gt;.</div> Cuozzo