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.