2026-07-22T14:20:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16143 2024-03-06T10:56:40Z ddc:004 open_access

On Strings Having the Same Length- k Substrings Bernardini, Giulia Conte, Alessio Gabory, Esteban Grossi, Roberto Loukides, Grigorios Pissis, Solon P. Punzi, Giulia Sweering, Michelle string algorithms combinatorics on words de Bruijn graph Chinese Postman Let Substr_k(X) denote the set of length-k substrings of a given string X for a given integer k > 0. We study the following basic string problem, called z-Shortest 𝒮_k-Equivalent Strings: Given a set 𝒮_k of n length-k strings and an integer z > 0, list z shortest distinct strings T₁,…,T_z such that Substr_k(T_i) = 𝒮_k, for all i ∈ [1,z]. The z-Shortest 𝒮_k-Equivalent Strings problem arises naturally as an encoding problem in many real-world applications; e.g., in data privacy, in data compression, and in bioinformatics. The 1-Shortest 𝒮_k-Equivalent Strings, referred to as Shortest 𝒮_k-Equivalent String, asks for a shortest string X such that Substr_k(X) = 𝒮_k. Our main contributions are summarized below: - Given a directed graph G(V,E), the Directed Chinese Postman (DCP) problem asks for a shortest closed walk that visits every edge of G at least once. DCP can be solved in 𝒪̃(|E||V|) time using an algorithm for min-cost flow. We show, via a non-trivial reduction, that if Shortest 𝒮_k-Equivalent String over a binary alphabet has a near-linear-time solution then so does DCP. - We show that the length of a shortest string output by Shortest 𝒮_k-Equivalent String is in 𝒪(k+n²). We generalize this bound by showing that the total length of z shortest strings is in 𝒪(zk+zn²+z²n). We derive these upper bounds by showing (asymptotically tight) bounds on the total length of z shortest Eulerian walks in general directed graphs. - We present an algorithm for solving z-Shortest 𝒮_k-Equivalent Strings in 𝒪(nk+n²log²n+zn²log n+|output|) time. If z = 1, the time becomes 𝒪(nk+n²log²n) by the fact that the size of the input is Θ(nk) and the size of the output is 𝒪(k+n²). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giulia Bernardini and Alessio Conte and Esteban Gabory and Roberto Grossi and Grigorios Loukides and Solon P. Pissis and Giulia Punzi and Michelle Sweering 2022 Is Part Of LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2022.16 urn:nbn:de:0030-drops-161439 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.16 eng https://creativecommons.org/licenses/by/4.0/legalcode