2011/06/30 by Sebastian Deorowicz, Deorowicz, Sebastian
Biochemistry, Genetics and Molecular Biology · Computer Science · #68W32 #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #cs.DS #msc:68W32 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1106.6342
6 pages
arxiv created 2011/06/30 · openalex publication_date 2011/06/30 · arxiv updated 2011/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of finding a longest common subsequence of two main sequences with some constraint that must be a substring of the result (STR-IC-LCS) was formulated recently. It is a variant of the constrained longest common subsequence problem. As the known algorithms for the STR-IC-LCS problem are cubic-time, the presented quadratic-time algorithm is significantly faster.