Longest common subsequence in sublinear space

We present the first o(n)-space polynomial-time algorithm for computing the length of a longest common subsequence. Given two strings of length n, the algorithm runs in O(n(3)) time with O (n log(1.5) n/2(root logn) bits of space. (C) 2021 Elsevier B.V. All rights reserved.

Automated summary

The algorithm presented is the first O(n)-space polynomial-time algorithm for computing the length of a longest common subsequence. It runs in O(n^3) time with O(n log(1.5) n/2(root logn) bits of space.