Faster Algorithms for Ranking/Unranking Bordered and Unbordered Words
摘要
We show how the arithmetic structure of the set of borders (periods) of a word can be used to substantially reduce complexity of an interesting problem in combinatorics on words. A word w is a bordered word if it has a non-empty proper border (a prefix which is a suffix); equivalently, it has a period smaller than |w|. Words which are not bordered are called unbordered. The problem of ranking/unranking such words of a given length n over an alphabet of size k was considered by Gabric (Inf. Process. Lett., 2024). We improve his results as follows: complexity of ranking is reduced by a factor \(nk/\log n\) and complexity of unranking by \(n^2k/ \log n\) (for large alphabets these improvement factors are \(n^2/\log n\) and \(n^3/ \log n\) , respectively). We use the unit-cost RAM model (the same model was used by Gabric).