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. 184, 106452, <CitationRef CitationID="CR6">2024</CitationRef>). We improve his results as follows: complexity of ranking is reduced by a factor <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$nk/\log n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mi>k</mi> <mo stretchy="false">/</mo> <mo>log</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> and complexity of unranking by <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$n^2 k \log k / \log n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>n</mi> <mn>2</mn> </msup> <mi>k</mi> <mo>log</mo> <mi>k</mi> <mo stretchy="false">/</mo> <mo>log</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> (for large alphabets these improvement factors are <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$n^2/\log n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">/</mo> <mo>log</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$n^3$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>n</mi> <mn>3</mn> </msup> </math></EquationSource> </InlineEquation>, respectively). Complexity of generation of unbordered words is also considered in the paper. We use the unit-cost RAM model (the same model was used by Gabric).

Faster Algorithms for Ranking/Unranking Bordered and Unbordered Words

期刊论文
发表日期：

2026年4月7日

查看全文

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. 184, 106452, 2024). We improve his results as follows: complexity of ranking is reduced by a factor $nk/\log n$ $n k / log n$ and complexity of unranking by $n^2 k \log k / \log n$ $n^{2} k log k / log n$ (for large alphabets these improvement factors are $n^2/\log n$ $n^{2} / log n$ and $n^3$ $n^{3}$ , respectively). Complexity of generation of unbordered words is also considered in the paper. We use the unit-cost RAM model (the same model was used by Gabric).