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>