.png){kind=icon}
.png){kind=icon}
Return
On Strings Having the Same Length-k Substrings
.png){kind=icon}
PRE
AI
DOI：10.1007/s00224-025-10240-z.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 S-k-Equivalent Strings: Given a set S-k of n length-k strings and an integer z>0, list z shortest distinct strings T-1,...,T-z such that Substr(k)(Ti)=S-k, for all i is an element of[1,z].The z-Shortest 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. The1-ShortestSk- Equivalent Strings, referred to as Shortest S-k-Equivalent String, asks for a shortest string X such that Substr(k)(X)=S-k.Our main contributions are as follows. 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 using an algorithm for min-costflow. We show, via a non-trivial reduction, that if Shortest S-k-Equivalent String over abinary alphabet has a near-linear-time solution then so does DCP. Secondly, we show that the length of a shortest string output by Shortest S-k-Equivalent String is in O(k+n(2)). We generalize this bound by showing that the total length of z shortest strings is in O(zk+zn(2)+z(2)n). We derive these upper bounds by showing(asymptotically tight) bounds on the total length of z shortest Eulerian walks in general directed graphs. Furthermore, we present an algorithm for solving z-Shortest S-k-Equivalent Strings in O(nk+n(2)log(2)n+zn(2)logn+|output|)time. If z=1, the time becomes O(nk+n(2)log(2)n)by the fact that the size of the input is (sic)(nk)and the size of the output is 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.
Keywords:
Directed Chinese postman
Eulerian walk
de Bruijn graph
Listing
Journal
T
IF:
0.4
Papers:
43
Citations:
0
Organization
View more organizations