Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(X)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mi mathvariant="bold-sans-serif">Substr</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">X</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> denote the set of length-<InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varvec{k}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </math></EquationSource> </InlineEquation> substrings of a given string <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\varvec{X}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">X</mi> </mrow> </math></EquationSource> </InlineEquation> for a given integer <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\varvec{k}>\varvec{0}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> <mo>></mo> <mrow> <mn mathvariant="bold">0</mn> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We study the following basic string problem, called <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\varvec{z}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> </math></EquationSource> </InlineEquation>-Shortest <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-Equivalent Strings: Given a set <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\varvec{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> </math></EquationSource> </InlineEquation> length-<InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\varvec{k}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </math></EquationSource> </InlineEquation> strings and an integer <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\varvec{z}>\varvec{0}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> <mo>></mo> <mrow> <mn mathvariant="bold">0</mn> </mrow> </mrow> </math></EquationSource> </InlineEquation>, list <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\varvec{z}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> </math></EquationSource> </InlineEquation> shortest distinct strings <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\varvec{T}_{\varvec{1}}\varvec{,\ldots ,}\varvec{T}_{\varvec{z}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mi mathvariant="bold-italic">T</mi> </mrow> <mrow> <mn mathvariant="bold">1</mn> </mrow> </msub> <mrow> <mo mathvariant="bold">,</mo> <mo mathvariant="bold">…</mo> <mo mathvariant="bold">,</mo> </mrow> <msub> <mrow> <mi mathvariant="bold-italic">T</mi> </mrow> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(}\varvec{T}_{\varvec{i}}\varvec{)}=\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mi mathvariant="bold-sans-serif">Substr</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <msub> <mrow> <mi mathvariant="bold-italic">T</mi> </mrow> <mrow> <mi mathvariant="bold-italic">i</mi> </mrow> </msub> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>, for all <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$\varvec{i}\,{\in }\,\varvec{[1,z]}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">i</mi> </mrow> <mspace width="0.166667em" /> <mo>∈</mo> <mspace width="0.166667em" /> <mrow> <mo mathvariant="bold" stretchy="false">[</mo> <mn mathvariant="bold">1</mn> <mo mathvariant="bold">,</mo> <mi mathvariant="bold-italic">z</mi> <mo mathvariant="bold" stretchy="false">]</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. The <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$\varvec{z}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> </math></EquationSource> </InlineEquation>-Shortest <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-Equivalent Strings problem arises naturally as an encoding problem in many real-world applications; e.g. in data privacy, data compression, and bioinformatics. The <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$\varvec{1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn mathvariant="bold">1</mn> </mrow> </math></EquationSource> </InlineEquation>-Shortest <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-Equivalent Strings, referred to as Shortest <InlineEquation ID="IEq19"> <EquationSource Format="TEX">$\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-Equivalent String, asks for a shortest string <InlineEquation ID="IEq20"> <EquationSource Format="TEX">$\varvec{X}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">X</mi> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq21"> <EquationSource Format="TEX">$\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(X)}=\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mrow> <mi mathvariant="bold-sans-serif">Substr</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">X</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>. Our main contributions are as follows. Given a directed graph <InlineEquation ID="IEq22"> <EquationSource Format="TEX">$\varvec{G}=\varvec{(V,E)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">G</mi> </mrow> <mo>=</mo> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">V</mi> <mo mathvariant="bold">,</mo> <mi mathvariant="bold-italic">E</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, the Directed Chinese Postman (DCP) problem asks for a shortest closed walk that visits every edge of <InlineEquation ID="IEq23"> <EquationSource Format="TEX">$\varvec{G}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">G</mi> </mrow> </math></EquationSource> </InlineEquation> at least once. DCP can be solved using an algorithm for min-cost flow. We show, via a non-trivial reduction, that if Shortest <InlineEquation ID="IEq24"> <EquationSource Format="TEX">$\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-Equivalent String over a binary alphabet has a near-linear-time solution then so does DCP. Secondly, we show that the length of a shortest string output by Shortest <InlineEquation ID="IEq25"> <EquationSource Format="TEX">$\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-Equivalent String is in <InlineEquation ID="IEq26"> <EquationSource Format="TEX">$\varvec{\mathcal {O}}\varvec{(}\varvec{k}+\varvec{n}^{\varvec{2}}\varvec{)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-script">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> <mo>+</mo> <msup> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We generalize this bound by showing that the total length of <InlineEquation ID="IEq27"> <EquationSource Format="TEX">$\varvec{z}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> </math></EquationSource> </InlineEquation> shortest strings is in <InlineEquation ID="IEq28"> <EquationSource Format="TEX">$\varvec{\mathcal {O}}\varvec{(}\varvec{zk}+\varvec{zn}^{\varvec{2}}+\varvec{z}^{\varvec{2}}\varvec{n}\varvec{)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-script">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">zk</mi> </mrow> <mo>+</mo> <msup> <mrow> <mi mathvariant="bold-italic">zn</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mo>+</mo> <msup> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We derive these upper bounds by showing (asymptotically tight) bounds on the total length of <InlineEquation ID="IEq29"> <EquationSource Format="TEX">$\varvec{z}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> </math></EquationSource> </InlineEquation> shortest Eulerian walks in general directed graphs. Furthermore, we present an algorithm for solving <InlineEquation ID="IEq30"> <EquationSource Format="TEX">$\varvec{z}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> </math></EquationSource> </InlineEquation>-Shortest <InlineEquation ID="IEq31"> <EquationSource Format="TEX">$\varvec{\mathcal {S}}_{\varvec{k}}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mrow> <mi mathvariant="bold-script">S</mi> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-Equivalent Strings in <InlineEquation ID="IEq32"> <EquationSource Format="TEX">$\varvec{\mathcal {O}}\varvec{(}\varvec{nk}+\varvec{n}^{\varvec{2}}\,\varvec{\log }^{\varvec{2}}\,\varvec{n}+\varvec{zn}^{\varvec{2}}\,\varvec{\log }\,\varvec{n}+|\varvec{\textsf {output}}|)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-script">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">nk</mi> </mrow> <mo>+</mo> <msup> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mspace width="0.166667em" /> <msup> <mrow> <mo mathvariant="bold">log</mo> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mspace width="0.166667em" /> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mo>+</mo> <msup> <mrow> <mi mathvariant="bold-italic">zn</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mspace width="0.166667em" /> <mrow> <mo mathvariant="bold">log</mo> </mrow> <mspace width="0.166667em" /> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mo>+</mo> <mrow> <mo stretchy="false">|</mo> <mrow> <mi mathvariant="bold-sans-serif">output</mi> </mrow> <mo stretchy="false">|</mo> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> time. If <InlineEquation ID="IEq33"> <EquationSource Format="TEX">$\varvec{z}=\varvec{1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-italic">z</mi> </mrow> <mo>=</mo> <mrow> <mn mathvariant="bold">1</mn> </mrow> </mrow> </math></EquationSource> </InlineEquation>, the time becomes <InlineEquation ID="IEq34"> <EquationSource Format="TEX">$\varvec{\mathcal {O}}\varvec{(}\varvec{nk}+\varvec{n}^{\varvec{2}}\,\varvec{\log }^{\varvec{2}}\,\varvec{n}\varvec{)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-script">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">nk</mi> </mrow> <mo>+</mo> <msup> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mspace width="0.166667em" /> <msup> <mrow> <mo mathvariant="bold">log</mo> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mspace width="0.166667em" /> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> by the fact that the size of the input is <InlineEquation ID="IEq35"> <EquationSource Format="TEX">$\varvec{\Theta }\varvec{(nk)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold">Θ</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> <mi mathvariant="bold-italic">n</mi> <mi mathvariant="bold-italic">k</mi> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and the size of the output is <InlineEquation ID="IEq36"> <EquationSource Format="TEX">$\varvec{\mathcal {O}}\varvec{(}\varvec{k}+\varvec{n}^{\varvec{2}}\varvec{)}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="bold-script">O</mi> </mrow> <mrow> <mo mathvariant="bold" stretchy="false">(</mo> </mrow> <mrow> <mi mathvariant="bold-italic">k</mi> </mrow> <mo>+</mo> <msup> <mrow> <mi mathvariant="bold-italic">n</mi> </mrow> <mrow> <mn mathvariant="bold">2</mn> </mrow> </msup> <mrow> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. Finally, we also provide a direct technical application of our algorithms on strings in an existing data privacy framework. A preliminary version of this paper was announced at CPM 2022.

On Strings Having the Same Length-k Substrings

期刊论文
出版模式：

开放获取
发表日期：

2026年4月1日

查看全文

Giulia Bernardini,
Alessio Conte,
Esteban Gabory,
Roberto Grossi,
Grigorios Loukides,
Solon P. Pissis,
Giulia Punzi,
Michelle Sweering

摘要

Let $\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(X)}$ ${Substr}_{k} (X)$ denote the set of length- $\varvec{k}$ $k$ substrings of a given string $\varvec{X}$ $X$ for a given integer $\varvec{k}>\varvec{0}$ $k > 0$ . We study the following basic string problem, called $\varvec{z}$ $z$ -Shortest $\varvec{\mathcal {S}}_{\varvec{k}}$ $S_{k}$ -Equivalent Strings: Given a set $\varvec{\mathcal {S}}_{\varvec{k}}$ $S_{k}$ of $\varvec{n}$ $n$ length- $\varvec{k}$ $k$ strings and an integer $\varvec{z}>\varvec{0}$ $z > 0$ , list $\varvec{z}$ $z$ shortest distinct strings $\varvec{T}_{\varvec{1}}\varvec{,\ldots ,}\varvec{T}_{\varvec{z}}$ $T_{1}, \dots, T_{z}$ such that $\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(}\varvec{T}_{\varvec{i}}\varvec{)}=\varvec{\mathcal {S}}_{\varvec{k}}$ ${Substr}_{k} (T_{i}) = S_{k}$ , for all $\varvec{i}\,{\in }\,\varvec{[1,z]}$ $i \in [1, z]$ . The $\varvec{z}$ $z$ -Shortest $\varvec{\mathcal {S}}_{\varvec{k}}$ $S_{k}$ -Equivalent Strings problem arises naturally as an encoding problem in many real-world applications; e.g. in data privacy, data compression, and bioinformatics. The $\varvec{1}$ $1$ -Shortest $\varvec{\mathcal {S}}_{\varvec{k}}$ $S_{k}$ -Equivalent Strings, referred to as Shortest $\varvec{\mathcal {S}}_{\varvec{k}}$ $S_{k}$ -Equivalent String, asks for a shortest string $\varvec{X}$ $X$ such that $\varvec{\textsf {Substr}}_{\varvec{k}}\varvec{(X)}=\varvec{\mathcal {S}}_{\varvec{k}}$ ${Substr}_{k} (X) = S_{k}$ . Our main contributions are as follows. Given a directed graph $\varvec{G}=\varvec{(V,E)}$ $G = (V, E)$ , the Directed Chinese Postman (DCP) problem asks for a shortest closed walk that visits every edge of $\varvec{G}$ $G$ at least once. DCP can be solved using an algorithm for min-cost flow. We show, via a non-trivial reduction, that if Shortest $\varvec{\mathcal {S}}_{\varvec{k}}$ $S_{k}$ -Equivalent String over a binary alphabet has a near-linear-time solution then so does DCP. Secondly, we show that the length of a shortest string output by Shortest $\varvec{\mathcal {S}}_{\varvec{k}}$ $S_{k}$ -Equivalent String is in $\varvec{\mathcal {O}}\varvec{(}\varvec{k}+\varvec{n}^{\varvec{2}}\varvec{)}$ $O (k + n^{2})$ . We generalize this bound by showing that the total length of $\varvec{z}$ $z$ shortest strings is in $\varvec{\mathcal {O}}\varvec{(}\varvec{zk}+\varvec{zn}^{\varvec{2}}+\varvec{z}^{\varvec{2}}\varvec{n}\varvec{)}$ $O (zk + {zn}^{2} + z^{2} n)$ . We derive these upper bounds by showing (asymptotically tight) bounds on the total length of $\varvec{z}$ $z$ shortest Eulerian walks in general directed graphs. Furthermore, we present an algorithm for solving $\varvec{z}$ $z$ -Shortest $\varvec{\mathcal {S}}_{\varvec{k}}$ $S_{k}$ -Equivalent Strings in $\varvec{\mathcal {O}}\varvec{(}\varvec{nk}+\varvec{n}^{\varvec{2}}\,\varvec{\log }^{\varvec{2}}\,\varvec{n}+\varvec{zn}^{\varvec{2}}\,\varvec{\log }\,\varvec{n}+|\varvec{\textsf {output}}|)$ $O (nk + n^{2} {log}^{2} n + {zn}^{2} log n + | output |)$ time. If $\varvec{z}=\varvec{1}$ $z = 1$ , the time becomes $\varvec{\mathcal {O}}\varvec{(}\varvec{nk}+\varvec{n}^{\varvec{2}}\,\varvec{\log }^{\varvec{2}}\,\varvec{n}\varvec{)}$ $O (nk + n^{2} {log}^{2} n)$ by the fact that the size of the input is $\varvec{\Theta }\varvec{(nk)}$ $Θ (n k)$ and the size of the output is $\varvec{\mathcal {O}}\varvec{(}\varvec{k}+\varvec{n}^{\varvec{2}}\varvec{)}$ $O (k + n^{2})$ . Finally, we also provide a direct technical application of our algorithms on strings in an existing data privacy framework. A preliminary version of this paper was announced at CPM 2022.