字符串

Definition. An alphabet is any set, most commonly a set of letters or numbers. We usually denote an alphabet by $\Sigma$ ("s"igma for "s"tring, probably).

Definition. A string is a sequence of elements from an alphabet. We generally denote the empty string by $\epsilon$.

Now let's look at the operations we can perform on strings.

Length. The length of the sequence the string represents. It is denoted by $|\cdot|$. For example $|abcd|=4$.

Substring. If our string is $s=s_0s_1s_2\dots$ then the substring starting at $i$ and ending at $j$ (denoted as $s[i,j)$) is the string $s_is_{i+1}\dots s_{j-1}$. This is only well-defined when $0\le i\le j-1$, but we also define the substring to be empty if $i=j$.

Concatenation. Take two strings and put them next to each other. For example the concatenation of $abc$ and $def$ is $abcdef$. The concatenation of $def$ and $abc$ is $defabc$.

Multiple concatenations. For a string $s$ and $n\in\mathbb N$ we denote $s^n$ as $s$ concatenated with itself $n$ times. In particular, $s^0=\epsilon$.

Finally, there is the notion of lexicographical order. First, someone must assign some order on the alphabet $\Sigma$. For example, I may order $\Sigma=\{0,1\}$ by $0<1$.

To determine the lexicographical order of two strings $s_1=a_0a_1a_2\dots$ and $s_2=b_0b_1b_2\dots$, we sequentially compare $a_0,b_0$, then $a_1,b_1$, etc., until we have some inequality. In particular, $s_1>s_2$ if and only if: $a_0>b_0$, or $a_0=b_0$ and $a_1>b_1$, or $a_0=b_0$ and $a_1=b_1$ and $a_2>b_2$, or $a_0=b_0$ and $a_1>b_1$, or $a_0=b_0$ and $a_1=b_1$ and $a_2=b_2$ and $a_3>b_3$, etc.

Also denote $\epsilon<s$ for all $s\in\Sigma$.