Ranking and unranking bordered and unbordered words

05/04/2023

∙

by   Daniel Gabric, et al.

∙

0

∙

share

A border of a word w is a word that is both a non-empty proper prefix and suffix of w. If w has a border, then it is said to be bordered; otherwise, it is said to be unbordered. The main results of this paper are the first algorithms to rank and unrank length-n bordered and unbordered words over a k-letter alphabet. We show that ranking bordered and unbordered words can be done in O(kn^3) time using O(n) space, and unranking them can be done in O(n^4klog k) time using O(n) space.