Approximating binary longest common subsequence in almost-linear time

Xiaoyu He, Ray Li

The Longest Common Subsequence (LCS) is a fundamental string similarity measure, and computing the LCS of two strings is a classic algorithms question. A textbook dynamic programmi…