Ranking and unranking bordered and unbordered words

05/04/2023
by   Daniel Gabric, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset