2020/08/04 by Sepideh Aghamolaei, Aghamolaei, Sepideh
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization #cs.DS
paper · pdf · doi:10.48550/arxiv.2008.01768
An optimal exact sketch for the LCS of two strings was already known: arXiv:1810.01238 as well as an approximation algorithm with weights: https://doi.org/10.1016/j.ic.2010.12.006 The edit distance of regular languages was also known: https://doi.org/10.3390/a11110165 Using these subroutines in any algorithm for the LCS of k strings gives a better result
openalex publication_date 2020/08/04 · arxiv created 2021/01/12 · arxiv updated 2021/01/13 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
Given a set of k strings I, their longest common subsequence (LCS) is the string with the maximum length that is a subset of all the strings in I. A data-structure for this problem preprocesses I into a data-structure such that the LCS of a set of query strings Q with the strings of I can be computed faster. Since the problem is NP-hard for arbitrary k, we allow an error that allows some characters to be replaced by other characters. We define the approximation version of the problem with an extra input m, which is the length of the regular expression (regex) that describes the input, and the approximation factor is the logarithm of the number of possibilities in the regex returned by the algorithm, divided by the logarithm regex with the minimum number of possibilities. Then, we use a tree data-structure to achieve sublinear-time LCS queries. We also explain how the idea can be extended to the longest increasing subsequence (LIS) problem.