Home

unbordered

Unbordered is a term used in combinatorics on words to describe a finite sequence, or word, over a finite alphabet that has no border. A border of a word w of length n is a nonempty string that is both a prefix and a suffix of w, with length k satisfying 1 ≤ k ≤ n−1. If no such k exists, w is unbordered. Put differently, an unbordered word has no nontrivial overlap between its prefix and its suffix.

Examples: over the binary alphabet {a, b}, the word "ab" has no border and is unbordered; "aba"

Unbordered words are a standard object of study in combinatorics on words and are related to related

See also: Border (string), Prefix function, Primitivity, Knuth–Morris–Pratt algorithm.

has
a
border
of
length
1
("a"),
so
it
is
bordered;
"abc"
is
unbordered
on
an
alphabet
with
at
least
three
symbols;
"abab"
has
a
border
of
length
2
("ab").
concepts
such
as
primitivity
and
overlaps.
They
are
also
used
in
the
analysis
of
prefix-function
algorithms,
including
the
Knuth–Morris–Pratt
(KMP)
algorithm,
where
borders
determine
how
much
of
a
previous
match
can
be
reused.