Given a binary string <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\omega $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation> over the alphabet <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\{0, 1\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, a vector (a, b) is a Parikh vector if and only if a factor of <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\omega $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation> contains exactly a occurrences of 0 and b occurrences of 1. Answering whether a vector is a Parikh vector of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\omega $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation> is known as the Binary Jumbled Indexing Problem (BJIP) or the Histogram Indexing Problem. Most solutions to this problem rely on an O(n) word-space index to answer queries in constant time, encoding the Parikh set of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\omega $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation>, i.e., all its Parikh vectors. Cunha et al. (Combinatorial Pattern Matching, 2017) introduced an algorithm (JBM2017), which computes the index table in <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$O(n+\rho ^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <msup> <mi>ρ</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time, where <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\rho $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ρ</mi> </math></EquationSource> </InlineEquation> is the number of runs of identical digits in <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\omega $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ω</mi> </math></EquationSource> </InlineEquation>, leading to <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$O(n^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> in the worst case. We prove that the average number of runs <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\rho $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ρ</mi> </math></EquationSource> </InlineEquation> is n/4, confirming the quadratic behavior also in the average-case. We propose a new algorithm, SFTree, which uses a suffix tree to remove duplicate substrings. Although SFTree also has an average-case complexity of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\varTheta (n^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Θ</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> due to the fundamental reliance on run boundaries, it achieves practical improvements by minimizing memory access overhead through vectorization. The suffix tree further allows distinct substrings to be processed efficiently, reducing the effective cost of memory access. As a result, while both algorithms exhibit similar theoretical growth, SFTree significantly outperforms others in practice. Our analysis highlights both the theoretical and practical benefits of the SFTree approach, with potential extensions to other applications of suffix trees.

Binary jumbled indexing: suffix tree histogram

期刊论文
出版模式：

开放获取
发表日期：

2026年3月14日

查看全文

Luís Cunha,
Mário Medina

摘要

Given a binary string $\omega $ $ω$ over the alphabet $\{0, 1\}$ ${0, 1}$ , a vector (a, b) is a Parikh vector if and only if a factor of $\omega $ $ω$ contains exactly a occurrences of 0 and b occurrences of 1. Answering whether a vector is a Parikh vector of $\omega $ $ω$ is known as the Binary Jumbled Indexing Problem (BJIP) or the Histogram Indexing Problem. Most solutions to this problem rely on an O(n) word-space index to answer queries in constant time, encoding the Parikh set of $\omega $ $ω$ , i.e., all its Parikh vectors. Cunha et al. (Combinatorial Pattern Matching, 2017) introduced an algorithm (JBM2017), which computes the index table in $O(n+\rho ^2)$ $O (n + ρ^{2})$ time, where $\rho $ $ρ$ is the number of runs of identical digits in $\omega $ $ω$ , leading to $O(n^2)$ $O (n^{2})$ in the worst case. We prove that the average number of runs $\rho $ $ρ$ is n/4, confirming the quadratic behavior also in the average-case. We propose a new algorithm, SFTree, which uses a suffix tree to remove duplicate substrings. Although SFTree also has an average-case complexity of $\varTheta (n^2)$ $Θ (n^{2})$ due to the fundamental reliance on run boundaries, it achieves practical improvements by minimizing memory access overhead through vectorization. The suffix tree further allows distinct substrings to be processed efficiently, reducing the effective cost of memory access. As a result, while both algorithms exhibit similar theoretical growth, SFTree significantly outperforms others in practice. Our analysis highlights both the theoretical and practical benefits of the SFTree approach, with potential extensions to other applications of suffix trees.