String Inference from Longest-Common-Prefix Array
String Inference from Longest-Common-Prefix Array
复制标题
DOI：
10.4230/lipics.icalp.2017.62
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Juha Kärkkäinen;Marcin Piatkowski;S. Puglisi
中科院分区：
文献类型：
--
作者：
Juha Kärkkäinen;Marcin Piatkowski;S. Puglisi
后缀阵列，也许是现代字符串处理中最重要的数据结构，通常会用最长的常见前缀（LCP）阵列增强，该阵列存储LCP的长度，用于字符串的词典相邻后缀。这两个阵列一起大致等于后缀树，其中LCP阵列代表树的形状。为了更好地了解LCP数组的组合学，我们考虑从LCP数组中推断字符串的问题，即确定给定的整数数组是有效的LCP数组，如果是，则重建一些字符串或所有字符串或所有字符串使用该LCP数组。最近有研究从后缀树形状推断一条字符串，但使用明显更多的信息（以后缀链接的形式）要比LCP阵列中可用。我们提供两个主要结果。 （1）当我们允许定义为多个循环字符串定义的广义形式的LCP阵列时，我们描述了两种用于从LCP阵列中推断字符串的算法：二进制字母的线性时间算法和具有恒定字母复杂性的一般算法的线性时间算法尺寸。 （2）我们证明，当我们需要针对单个循环或非循环字符串定义的更多受限形式的LCP数组或多个非循环字符串定义的LCP阵列时，确定给定整数数组是有效的LCP数组。结果认为字母是否仅限于二进制。结合起来，这两个结果表明，多种环状字符串的LCP阵列的广义形式与其他更受限制的形式根本不同。
The suffix array, perhaps the most important data structure in modern string processing, is often augmented with the longest common prefix (LCP) array which stores the lengths of the LCPs for lexicographically adjacent suffixes of a string. Together the two arrays are roughly equivalent to the suffix tree with the LCP array representing the tree shape. In order to better understand the combinatorics of LCP arrays, we consider the problem of inferring a string from an LCP array, i.e., determining whether a given array of integers is a valid LCP array, and if it is, reconstructing some string or all strings with that LCP array. There are recent studies of inferring a string from a suffix tree shape but using significantly more information (in the form of suffix links) than is available in the LCP array. We provide two main results. (1) We describe two algorithms for inferring strings from an LCP array when we allow a generalized form of LCP array defined for a multiset of cyclic strings: a linear time algorithm for binary alphabet and a general algorithm with polynomial time complexity for a constant alphabet size. (2) We prove that determining whether a given integer array is a valid LCP array is NP-complete when we require more restricted forms of LCP array defined for a single cyclic or non-cyclic string or a multiset of non-cyclic strings. The result holds whether or not the alphabet is restricted to be binary. In combination, the two results show that the generalized form of LCP array for a multiset of cyclic strings is fundamentally different from the other more restricted forms.