On Strings Having the Same Length-k Substrings

doi:10.1007/s00224-025-10240-z

On Strings Having the Same Length-k Substrings

2026-04-01

0

PRE

AI

DOI：10.1007/s00224-025-10240-z

原文链接

原文求助

摘要

En 中文

设Substr(k)(X)表示给定字符串X的所有长度为k的子串集合，其中k为给定整数且k>0。我们研究了如下基本字符串问题，称为z-最短S-k-等价字符串问题：给定一个包含n个长度为k的字符串的集合S-k和整数z>0，列出z个最短的互异字符串T-1,...,T-z，使得对于所有i∈[1,z]，Substr(k)(Ti)=S-k。z-最短S-k-等价字符串问题在许多实际应用中自然地表现为编码问题；例如在数据隐私、数据压缩和生物信息学中。1-最短S-k-等价字符串问题（简称为最短S-k-等价字符串问题）要求一个最短字符串X，使得Substr(k)(X)=S-k。我们的主要贡献如下。给定有向图G=(V,E)，有向中国邮路问题(DCP)要求一条最短的闭迹，使得每条边至少被访问一次。DCP可通过最小费用流算法求解。我们通过一个非平凡的归约证明，如果二元字母表上的最短S-k-等价字符串问题存在近线性时间解，则DCP也存在近线性时间解。其次，我们证明最短S-k-等价字符串输出的最短字符串长度为O(k+n²)。我们推广此界，证明z个最短字符串的总长度为O(zk+zn²+z²n)。我们通过证明一般有向图中z条最短欧拉迹的总长度（渐近紧界）来推导这些上界。此外，我们提出了一个在O(nk+n²log²n+zn²logn+|输出|)时间内求解z-最短S-k-等价字符串问题的算法。当z=1时，时间复杂度变为O(nk+n²log²n)，这是因为输入规模为Θ(nk)，输出规模为O(k+n²)。最后，我们将算法在字符串上的直接技术应用于现有数据隐私框架。本文的初步版本曾在CPM 2022上公布。

Keyword:

Directed Chinese postman

Eulerian walk

de Bruijn graph

Listing

On Strings Having the Same Length-k Substrings

摘要

期刊

机构

引用论文