  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 programming algorithm gives an exact algorithm in quadratic
time, and this is essentially best possible under plausible fine-grained
complexity assumptions, so a natural problem is to find faster approximation
algorithms. When the inputs are two binary strings, there is a simple
$\frac{1}{2}$-approximation in linear time: compute the longest common all-0s
or all-1s subsequence. It has been open whether a better approximation is
possible even in truly subquadratic time. Rubinstein and Song showed that the
answer is yes under the assumption that the two input strings have equal
lengths. We settle the question, generalizing their result to unequal length
strings, proving that, for any $\varepsilon>0$, there exists $\delta>0$ and a
$(\frac{1}{2}+\delta)$-approximation algorithm for binary LCS that runs in
$n^{1+\varepsilon}$ time. As a consequence of our result and a result of Akmal
and Vassilevska-Williams, for any $\varepsilon>0$, there exists a
$(\frac{1}{q}+\delta)$-approximation for LCS over $q$-ary strings in
$n^{1+\varepsilon}$ time.
  Our techniques build on the recent work of Guruswami, He, and Li who proved
new bounds for error-correcting codes tolerating deletion errors. They prove a
combinatorial "structure lemma" for strings which classifies them according to
their oscillation patterns. We prove and use an algorithmic generalization of
this structure lemma, which may be of independent interest.
