Combinatorics · Lesson 6

Generating Bordered Words

Practice this topic →

The shortest border is unbordered

A word can have many borders, but its shortest border is special.

Unbordered. Any border of $x$ would be a prefix of $w$ and a suffix of $w$ (since $x$ is both), hence a border of $w$ shorter than $x$ — impossible.

At most half. If $\left|x\right|=m>n/2$, the length-$(n-m)$ prefix of $x$ matches the corresponding suffix, giving a border of $w$ shorter than $x$ — again impossible. So $m\le n/2$.

Every bordered word is $xzx$

The two observations above collapse into a clean characterization.

The word $x$ is the shortest border of $w$; the middle $z$ is the unique segment $w[m+1..n-m]$. Uniqueness is exactly why classifying words by their shortest border is the right way to count and to generate.

Why the decomposition works

Only bordered. If $x$ is unbordered and $\left|x\right|=m\le n/2$, then $x$ is a prefix and a suffix of $xzx$, so the word is bordered and has a proper border of length $m$.

All, with $x$ the shortest. Any border of $xzx$ of length $<m$ would be a prefix of $x$ and a suffix of $x$, i.e. a border of $x$. Since $x$ is unbordered, no such border exists. So the decomposition recovers exactly the shortest border — every bordered word is produced, each exactly once.

Counting sanity check. This is why $u_k\left(n\right)$ alone could not count bordered words: the number of bordered words of length $n$ is

which equals $k^n-u_k\left(n\right)$.

Efficiency

The GenB algorithm loops over the shortest-border length $m$, runs GenU to produce the unbordered words $x$ of length $m$, and for each $x$ runs an odometer over the $k^{n-2m}$ choices of $z$.

Every recursive step of GenU and every odometer increment produces at least one output word, and there are at least as many outputs as calls to GenU overall (each $x$ yields at least one $z$). Excluding the cost of writing each word out, GenB runs in constant-amortized time.

Practice

Which words are bordered?

Practice this topic →Every quiz from this lesson, at four difficulties.