On Strings Having the Same Length-k Substrings

Abstract Let $$\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(X)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mi>Substr</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>X</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> denote the set of length- $$\varvec{k}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> substrings of a given string $$\varvec{X}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> for a given integer $$\varvec{k}&gt;\varvec{0}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mrow> <mml:mn>0</mml:mn> </mml:mrow> </mml:mrow> </mml:math> . We study the following basic string problem, called $$\varvec{z}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>z</mml:mi> </mml:mrow> </mml:math> - Shortest $$\varvec{\mathcal {S}}_{\varvec{k}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mi>S</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:msub> </mml:math> - Equivalent Strings : Given a set $$\varvec{\mathcal {S}}_{\varvec{k}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mi>S</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:msub> </mml:math> of $$\varvec{n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> length- $$\varvec{k}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> strings and an integer $$\varvec{z}&gt;\varvec{0}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>z</mml:mi> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mrow> <mml:mn>0</mml:mn> </mml:mrow> </mml:mrow> </mml:math> , list $$\varvec{z}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>z</mml:mi> </mml:mrow> </mml:math> shortest distinct strings $$\varvec{T}_{\varvec{1}}\varvec{,\ldots ,}\varvec{T}_{\varvec{z}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> </mml:mrow> <mml:msub> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>z</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> such that $$\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(}\varvec{T}_{\varvec{i}}\varvec{)}=\varvec{\mathcal {S}}_{\varvec{k}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mi>Substr</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:msub> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow>

Authors

Institutions

Publication Details

Journal
Theory of Computing Systems
Published
2026-04-01
DOI
https://doi.org/10.1007/s00224-025-10240-z
Primary Topic
Algorithms and Data Compression
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

On Strings Having the Same Length-k Substrings

Michelle Sweering, Solon P. Pissis, Estéban Gabory, Grigorios Loukides et al.
Theory of Computing Systems
Algorithms and Data Compression
article

On Strings Having the Same Length-k Substrings

Michelle Sweering, Solon P. Pissis, Estéban Gabory, Grigorios Loukides, Giulia Bernardini, Alessio Conte, Giulia Punzi, Roberto Grossi
article en

Abstract

Abstract Let $$\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(X)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mi>Substr</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>X</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> denote the set of length- $$\varvec{k}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> substrings of a given string $$\varvec{X}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> for a given integer $$\varvec{k}&gt;\varvec{0}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mrow> <mml:mn>0</mml:mn> </mml:mrow> </mml:mrow> </mml:math> . We study the following basic string problem, called $$\varvec{z}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>z</mml:mi> </mml:mrow> </mml:math> - Shortest $$\varvec{\mathcal {S}}_{\varvec{k}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mi>S</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:msub> </mml:math> - Equivalent Strings : Given a set $$\varvec{\mathcal {S}}_{\varvec{k}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mi>S</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:msub> </mml:math> of $$\varvec{n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> length- $$\varvec{k}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> strings and an integer $$\varvec{z}&gt;\varvec{0}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>z</mml:mi> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mrow> <mml:mn>0</mml:mn> </mml:mrow> </mml:mrow> </mml:math> , list $$\varvec{z}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>z</mml:mi> </mml:mrow> </mml:math> shortest distinct strings $$\varvec{T}_{\varvec{1}}\varvec{,\ldots ,}\varvec{T}_{\varvec{z}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> </mml:mrow> <mml:msub> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>z</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> such that $$\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(}\varvec{T}_{\varvec{i}}\varvec{)}=\varvec{\mathcal {S}}_{\varvec{k}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mrow> <mml:mi>Substr</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> </mml:mrow> <mml:msub> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow>

Theory of Computing SystemsVol. 70(2)
University of Pisa (IT), Centrum Wiskunde & Informatica (NL), King's College London (GB), University of Milan (IT), University of Palermo (IT)
Ministero dell’Istruzione, dell’Università e della Ricerca, Ministero dell'Università e della Ricerca, Gruppo Nazionale per il Calcolo Scientifico, Horizon 2020, NextGenerationEU
Openalex Percentile: Top 14%
Algorithms and Data Compression
DOIOpen Access PDFOpenAlex
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.