Journal
INFORMATION PROCESSING LETTERS
Volume 168, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.ipl.2020.106084
Keywords
Computational complexity; Space-efficient algorithm; Longest common subsequence; Levenshtein distance
Categories
Funding
- JSPS KAKENHI [JP18H04091, JP18K11153, JP18K11168, JP18K11169]
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
