## Example

\(
\def\sa#1{\tt{#1}}
\def\alph{\mathit{alph}}
\def\mv{\varepsilon}
\def\Fact{\mathit{Fact}}
\def\Pref{\mathit{Pref}}
\def\Suff{\mathit{Suff}}
\def\dd{\dot{}\dot{}}
\)

For $x=\sa{abaaab}$ we have $|x|=6$ and $\alph(x)=\{\sa{a},\sa{b}\}$.

The set of conjugates of $\sa{abba}$, its conjugacy class
because conjugacy is an equivalence relation, is
$\{\sa{aabb},\sa{abba},\sa{baab},\sa{bbaa}\}$ and
that of $\sa{abab}$ is $\{\sa{abab},\sa{baba}\}$.

The starting and ending positions of
$x=\sa{aba}$ on $y=\sa{babaababa}$ are:

$i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

$y[i]$ | $\sa{b}$ | $\sa{a}$ | $\sa{b}$ | $\sa{a}$ | $\sa{a}$ | $\sa{b}$ | $\sa{a}$ | $\sa{b}$ | $\sa{a}$ |

starting positions | | 1 | | | 4 | | 6 | | |

ending positions | | | | 3 | | | 6 | | 8 |

#
Words

An *alphabet* is a non-empty set whose elements are called
*letters* or symbols.
We typically use alphabets
$\mathbf{A}=\{\sa{a},\sa{b},\sa{c},\dots\}$, $\mathbf{B}=\{\sa{0},\sa{1}\}$
and natural numbers.
A *word* (*mot*, in French) or *string* on an
alphabet $A$ is a sequence of elements of $A$.

The zero letter sequence is called the empty word and is
denoted by $\mv$.
The set of all finite words on an alphabet $A$ is denoted
by $A^*$, and $A^+=A^*\setminus\{\mv\}$.

The *length* of a word $x$, length of the sequence, is denoted by $|x|$.
We denote by $x[i]$, for $i=0,1,\dots,|x|-1$, the letter at *position*
or *index* $i$ on a non-empty word $x$.
Then $x=x[0] x[1] \cdots x[|x|-1]$ also denoted by $x[0\dd |x|-1]$.
The set of letters that occur in the word $x$ is denoted by $\alph(x)$.

The *product* or *concatenation* of two words $x$ and $y$
is the word composed of the letters of $x$ followed by the letters of $y$.
It is denoted by $xy$, or by $x\cdot y$
to emphasise the decomposition of the resulting word.
The neutral element for the product is $\mv$ and we denote respectively by
$zy^{-1}$ and $x^{-1}z$ the words $x$ and $y$ when $z=xy$.

A *conjugate*, *rotation* or
*cyclic shift* of a word $x$ is any
word $y$ that factorises into $vu$, where $uv=x$.
This makes sense because the product of words is obviously non-commutative.

A word $x$ is a *factor* (sometimes called
*substring*) of a word $y$
if $y=uxv$ for two words $u$ and $v$.
When $u=\mv$, $x$ is a *prefix* of $y$, and when $v=\mv$, $x$ is a
*suffix* of $y$.
Sets $\Fact(x)$, $\Pref(x)$ and $\Suff(x)$ denote the sets of factors,
prefixes and suffixes of $x$ respectively.

When $x$ is a non-empty factor of $y=y[0\dd n-1]$ it is of the form
$y[i\dd i+|x|-1]$ for some $i$.
An *occurrence* of $x$ in $y$ is an interval $[i\dd i+|x|-1]$ for which
$x=y[i\dd i+|x|-1]$.
We say that $i$ is the *starting position* (or left position) on $y$ of this
occurrence, and that $i+|x|-1$ is its *ending position* (or right
position).
An occurrence of $x$ in $y$ can also be defined as a triple
$(u,x,v)$ such that $y=uxv$.
Then the starting position of the occurrence is $|u|$.

For words $x$ and $y$, $|y|_x$ denotes the number of occurrences of $x$ in $y$.
Then, for instance, $|y|=\Sigma\{|y|_a \mid a\in\alph(y)\}$.

The word $x$ is a *subsequence* or *subword* of $y$ if the latter decomposes into
$w_0 x[0] w_1 x[1]\dots x[|x|-1] w_{|x|}$ for words $w_0$,
$w_1$, \dots, $w_{|x|}$.

A factor or a subsequence $x$ of a word $y$ is said to be
*proper* if $x\ne y$.