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).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Faster Algorithms for Ranking/Unranking Bordered and Unbordered Words

  • Jakub Radoszewski,
  • Wojciech Rytter,
  • Tomasz Waleń

摘要

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).