Ranking and unranking bordered and unbordered words
Daniel Gabrić · Information Processing Letters · 2023
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, under the unit-cost RAM model, ranking bordered and unbordered words can be done in O ( k n 3 ) time using O ( n ) space, and unranking them can be done in O ( n 4 k log k ) time using O ( n ) space.