Editing String
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 2: | Line 2: | ||
==Definitions== | ==Definitions== | ||
− | An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. (Since the alphabet is finite, we can always impose a total order when it would be useful to do so, such as when constructing a [[dictionary]].) An element of this the alphabet is known as a '''character'''. | + | An '''alphabet''', usually denoted <math>\Sigma</math> is a finite nonempty set (whose size is denoted <math>|\Sigma|</math>). It is often assumed that the alphabet is totally ordered, but this is not always necessary. (Since the alphabet is finite, we can always impose a total order when it would be useful to do so, such as when constructing a [[dictionary]].) An element of this the alphabet is known as a '''character'''. The size of the alphabet can affect the asymptotic complexity of string algorithms. In particular, if <math>N</math> is the size of the input, and the alphabet size is bounded by a constant independent of <math>N</math>, then it is called a '''constant''' alphabet; if its size is <math>O(N)</math>, it is called '''integer''' alphabet; and if it is larger than this then it is called a '''general''' alphabet. |
The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>|S|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.) | The set of <math>n</math>-tuples of <math>\Sigma</math> is denoted <math>\Sigma^n</math>. A '''string of length <math>n</math>''' is an element of <math>\Sigma^n</math>. The set <math>\Sigma^*</math> is defined <math>\Sigma^0 \cup \Sigma^1 \cup ...</math>; an element of <math>\Sigma^*</math> is known simply as a '''string''' over <math>\Sigma</math>. The '''empty string''', denoted <math>\epsilon</math> or <math>\lambda</math>, is the unique element of <math>\Sigma^0</math>. The length of a string <math>S</math> is denoted <math>|S|</math>. (Note that the usual definition of "string" requires strings to have finite length, although arbitrarily long strings exist.) | ||
Line 29: | Line 29: | ||
* <math>|ST| = |S|+|T|</math> | * <math>|ST| = |S|+|T|</math> | ||
For example, concatenating ''there'' and ''in'' gives ''therein''. So do concatenating ''the'' and ''rein'', or <math>\epsilon</math> and ''therein'', or ''therein'' and <math>\epsilon</math>. Note that in general, concatenation is not commutative. | For example, concatenating ''there'' and ''in'' gives ''therein''. So do concatenating ''the'' and ''rein'', or <math>\epsilon</math> and ''therein'', or ''therein'' and <math>\epsilon</math>. Note that in general, concatenation is not commutative. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Treatment in programming languages== | ==Treatment in programming languages== | ||
Line 50: | Line 40: | ||
* ''Find'' the first occurrence of a given character in a given string, or find the first occurrence of a given string as a substring of another string. | * ''Find'' the first occurrence of a given character in a given string, or find the first occurrence of a given string as a substring of another string. | ||
* ''Compare'' two strings [[Lexicographic order|lexicographically]]. | * ''Compare'' two strings [[Lexicographic order|lexicographically]]. | ||
− | |||
− | |||
− |