Chain (Border, String)

Definition

Chain (Border, String)

Of two borders of the same string, the shorter is a border of the longer. For strings $X,Y,S$,

$$X\text{ and }Y\text{ are borders of }S,|X|<|Y|⟹X\text{ is a border of }Y.$$

Thus the borders of $S$ form a nested chain: ordering them by length also orders them by the border relation. Two borders of equal length are the same string, since both are the prefix of $S$ of that length.

Why the Shorter Border Fits Inside the Longer

Here we do not start by knowing that $X$ is a border of $Y$. We know only that both strings occur at both ends of $S$, and that $X$ is shorter.

The shared ends force nesting

The longer border $Y$ begins and ends with the shorter border $X$.

Proof

• At the beginning of $S$: both $X$ and $Y$ start at the first character. Since $|X|<|Y|$, the whole occurrence of $X$ lies in the beginning of $Y$. Hence $X$ is a prefix of $Y$.
• At the end of $S$: both $X$ and $Y$ finish at the last character. Since $|X|<|Y|$, the whole occurrence of $X$ lies in the end of $Y$. Hence $X$ is a suffix of $Y$.

These are occurrences of the same string $Y$. Together they show that $Y$ begins and ends with $X$.

Transitivity goes in a different direction: it starts with $X$ a border of $Y$ and $Y$ a border of $S$, then concludes that $X$ is a border of $S$. The chain result starts with two borders of $S$ and establishes the relation between them.

Following the Chain

If $Y$ is the longest proper border of a non-empty string $S$, every border of $S$ shorter than $Y$ is a border of $Y$. Conversely, every proper border of $Y$ is a border of $S$ by transitivity.

Consequently, repeatedly taking the longest proper border visits all proper borders in decreasing length, ending at the empty string. No shorter border is lost by moving from $S$ to $Y$.

Examples

Two borders of ababa

Let $S=\mathrm{ababa}$. Both $X=\mathrm{a}$ and $Y=\mathrm{aba}$ are borders of $S$.

At the beginning of $S$, $\mathrm{a}$ is the first character of $\mathrm{aba}$. At the end of $S$, $\mathrm{a}$ is the last character of $\mathrm{aba}$. Thus $\mathrm{a}$ is itself a border of $\mathrm{aba}$.

The longest-proper-border chain is

$$\mathrm{ababa}⟶\mathrm{aba}⟶\mathrm{a}⟶\epsilon .$$