Chain (Border, String)

Definition

Chain (Border, String)

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

Thus the borders of 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 of that length.

Why the Shorter Border Fits Inside the Longer

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

The shared ends force nesting

The longer border begins and ends with the shorter border .

Proof

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

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

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

Following the Chain

If is the longest proper border of a non-empty string , every border of shorter than is a border of . Conversely, every proper border of is a border of 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 to .

Examples

Two borders of ababa

Let . Both and are borders of .

At the beginning of , is the first character of . At the end of , is the last character of . Thus is itself a border of .

The longest-proper-border chain is