String Border

computation

Definition

String Border

A string $X$ is a border of a string $S$ if $X$ is both a prefix and a suffix of $S$.

Trivial

Definition

Trivial String Border

Given a string $S$, then $\epsilon$, the empty string, and $S$, the string itself, are called trivial string borders.

Link to original

Chain

The borders of a string $S$ are totally ordered by length. If $X$ and $Y$ are borders of $S$ with $|X|<|Y|$, then $X$ is a border of $Y$. Equivalently, every border of $S$ is also a border of the longest border of $S$ (the maximal border).

Transitivity

If $Y$ is a border of $S$ and $X$ is a border of $Y$, then $X$ is a border of $S$. That is, the border relation is transitive.

Examples

$S=\text{ababa}$

The borders are $\epsilon$, $\text{a}$, and $\text{aba}$.

$S=\text{abcab}$

The borders are $\epsilon$ and $\text{ab}$.

$S=\text{aaaa}$

The borders are $\epsilon$, $\text{a}$, $\text{aa}$, and $\text{aaa}$. The full string itself is not a border.