Algorithm improves time for approximate longest common subsequence
An $n^{8/5+o(1)}$-Time $Ω(λ^3)$-Approximation for Longest Common Subsequence
Data Structures and Algorithms
Summary
Finding the longest common subsequence (LCS) between two strings is a key problem in computer science, useful in areas like text comparison and bioinformatics. The difficulty increases with string length, making exact solutions slow. The authors improved an existing method to find an approximate solution much faster, specifically reducing the computation time from about n¹·⁹⁵ to n¹·⁶, where n is the string length. Their approximation guarantees a solution that is at least proportional to the cube of the true LCS ratio, offering a faster but still reliable approach.
What this means in practice
- •For software engineers: Implement faster similarity checks between text files or codebases using the improved approximate LCS algorithm.
- •For bioinformatics tool developers: Speed up DNA or protein sequence comparison by integrating the faster approximate longest common subsequence method.
Authors
Zhao Song
Abstract
Let $λ$ denote the ratio of the length of a longest common subsequence of two length-$n$ strings to $n$. Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $Ω(λ^3)$-approximation for LCS running in $\widetilde O(n^{39/20})$ time, where $39/20=1.95$. Song [Son19] mentioned that improving the $n^{1.95}$ running time is an interesting open question. We give an algorithm that computes an $Ω(λ^3)$-approximation of the longest common subsequence in $n^{8/5+o(1)}$ time. This improves the exponent $1.95$ to $1.6+o(1)$.