English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Longest Common Subsequence (LCS) of two strings is a fundamental stringsimilarity measure with a classical dynamic programming solution takingquadratic time. Despite significant efforts, little progress was made inimproving the runtime. Even in the realm of approximation, not much was knownfor linear time algorithms beyond the trivial $\sqrt{n}$-approximation. Recentbreakthrough result provided a $n^{0.497}$-factor approximation algorithm[HSSS19], which was more recently improved to a $n^{0.4}$-factor one [BCD21].The latter paper also showed a $n^{2-2.5\alpha}$ time algorithm which outputs a$n^{\alpha}$ approximation to the LCS, but so far no sub-polynomialapproximation is known in truly subquadratic time.  In this work, we show an algorithm which runs in $O(n)$ time, and outputs a$n^{o(1)}$-factor approximation to LCS$(x,y)$, with high probability, for anypair of length $n$ input strings.  Our entire algorithm is merely an efficient black-box reduction to theBlock-LIS problem, introduced very recently in [ANSS21], and solving theBlock-LIS problem directly.

Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time