In the word RAM model, a string T of length n over an integer alphabet of size <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>σ</mi> </math></EquationSource> </InlineEquation> can be represented in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {O}(n /\log _\sigma n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">/</mo> <msub> <mo>log</mo> <mi>σ</mi> </msub> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> space. We show that a representation of all covers of T can be computed in the optimal <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {O}(n/\log _\sigma n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">/</mo> <msub> <mo>log</mo> <mi>σ</mi> </msub> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time; in particular, the shortest cover can be computed within this time. We also design an <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathcal {O}(n\log \log n/\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-sized data structure that computes in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mathcal {O}(1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time any element of the so-called (shortest) cover array of T, that is, the length of the shortest cover of any given prefix of T. As a by-product, we describe the structure of the cover array of Fibonacci strings. On the negative side, we show that the shortest cover of a length-n string cannot be computed using <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$o(n/\log n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>o</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">/</mo> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> operations in the <Emphasis FontCategory="NonProportional">PILLAR</Emphasis> model of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020). This is an extended version of a paper published at SPIRE 2024 under the same title.

Computing String Covers in Sublinear Time

期刊论文
发表日期：

2026年2月7日

查看全文

Jakub Radoszewski,
Wiktor Zuba

摘要

In the word RAM model, a string T of length n over an integer alphabet of size $\sigma $ $σ$ can be represented in $\mathcal {O}(n /\log _\sigma n)$ $O (n / {log}_{σ} n)$ space. We show that a representation of all covers of T can be computed in the optimal $\mathcal {O}(n/\log _\sigma n)$ $O (n / {log}_{σ} n)$ time; in particular, the shortest cover can be computed within this time. We also design an $\mathcal {O}(n\log \log n/\log n)$ $O (n log log n / log n)$ -sized data structure that computes in $\mathcal {O}(1)$ $O (1)$ time any element of the so-called (shortest) cover array of T, that is, the length of the shortest cover of any given prefix of T. As a by-product, we describe the structure of the cover array of Fibonacci strings. On the negative side, we show that the shortest cover of a length-n string cannot be computed using $o(n/\log n)$ $o (n / log n)$ operations in the PILLAR model of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020). This is an extended version of a paper published at SPIRE 2024 under the same title.