Strings

This chapter covers notes on strings-related algorithms.

Definitions
k-Permutation String

In today's world, there's no such thing as a "string." There are ASCII strings and Unicode strings. While we can classify them as a single type "string," that classification isn't very useful — they're different enough that we must treat them separately. Accordingly, whenever we work with "strings," we must always — always — ask: Are working with ASCII strings or Unicode string?

Definitions

alphabet. A non-empty set of symbols is called an alphabet, denoted ${\Sigma.}$

For example, the set ${\set{0,1}}$ is an alphabet of two symbols. The set ${\set{a,b,c,d}}$ is an alphabet of four symbols.

string. Given an alphabet ${\Sigma,}$ the finite sequence

{\omega} = \omega_i = \ar{{\omega}_0~~~{\omega}_1~~~{\omega}_2~~~\ldots~~~{\omega}_{n-1}}

with ${\omega_i \in \Sigma}$ and ${n \in \nat}$ is called a string over ${\Sigma}$ of length ${n.}$ Given a symbol ${\omega_i,}$ we say that ${\omega_0}$ is the first symbol, and ${\omega_{n-1}}$ is the last symbol. We may denote the character o We denote the length ${n}$ of ${\omega}$ as ${\len(\omega).}$ If ${\len(\omega)=0,}$ then we call the ${\omega}$ the empty string, and denote it ${\epsilon.}$

Note that we will denote strings with double quotes. Thus, the string cookie is denoted ${{cookie}.}$ The string ${2 \pi r}$ is denoted ${{2 \pi r}.}$ Additionally, the empty string may also be denoted with the Greek letter ${\lambda.}$

Because how small subscripts are, we will adopt a few conventions when working with strings. First, given a string ${S,}$ we will reference the first character with ${S \ix{i},}$ where ${i}$ is an index. For example, given the string cake, writing ${{cake}\ix{0}}$ returns the string ${{c},}$ and writing ${{cake}\ix{2}}$ returns the string ${{k}.}$

kleene closure. Given an alphabet ${\Sigma,}$ the set of all strings over ${\Sigma}$ is called the Kleene closure of ${\Sigma,}$ denoted ${\Sigma^*.}$

language. Given a Kleene closure ${\Sigma^*}$ and a set of strings ${\cal{L},}$ if ${\cal{L} \subseteq \Sigma^*,}$ then ${\cal{L}}$ is a language.

word. Given a language ${\cal{L},}$ we call each string ${\ell \in \cal{L}}$ a word.

character. Given a word ${W = {c_0 ~ c_1 ~ \ldots ~ c_{n-1}}}$ of length ${n,}$ we call each symbol ${c_i \in \ell}$ with ${i = 0,1,\ldots,n-1}$ a character.

character encoding. Let ${C}$ denote a character set, and ${\set{x_i}_{i=1}^{n}}$ denote a finite range of integers ${\set{x_0, x_1, \ldots, x_{n}}}$ . Then the injection

\df{encode} : \set{x_i}_{i=1}^n \inj C

is called a character encoding, whose domain is called the code space ${\dom{\df{encode}},}$ and whose image ${\image{\df{(encode)}}}$ is called the coded character set. For each ${(x_i, c) \in \df{encode},}$ we call ${c}$ the coded character, and ${x_i}$ by the code point of ${c.}$

k-Permutation String

Given an alphabet ${\Sigma,}$ we define a k-permutation string as a permutation of a subset of ${\Sigma.}$ That is, a string composed entirely of distinct symbols.

k-permutation?

Let ${S}$ be a finite, non-empty string ${s_0,s_1,\ldots,s_{n-1}}$ over an alphabet ${\Sigma.}$ The function ${\df{k-permutation?}}$ returns ${0}$ if, and only if, each ${s_i}$ with ${0 \lt i \lt n-1}$ and ${i,n \in \nat}$ is distinct.

${\let{L}{\len{S}}}$
${\let{seen}{\df{new}~\df{hash-table}}}$
${seen \Lleftarrow (S_0, 0)}$
${\let{i}{1}}$
while ${i \lt L}$ do
1. if ${S_i \in seen}$ then return ${0}$
2. else ${seen \Lleftarrow (S_i, i)}$
3. ${i \inc}$
return ${1}$