Theory of Computing Systems Computational Theory and Mathematics
On Strings Having the Same Length-k Substrings
Abstract
Abstract 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 , … , 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 ∈ [ 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.