What question did this study set out to answer?

The aim is to develop an efficient algorithm for enumerating all longest common subsequences (LCSs) of two strings while managing space and delay.

March 12, 2026

A space-delay tradeoff algorithm for LCS enumeration of two strings

Key Points

The aim is to develop an efficient algorithm for enumerating all longest common subsequences (LCSs) of two strings while managing space and delay.
Proposed an O(n²-α)-space algorithm for LCS enumeration
Achieved O(n¹+α log² n) time complexity for each LCS after preprocessing
Utilized O(n²)-time preprocessing for input strings
Outputs all LCSs efficiently for given strings
Balances tradeoff between delay time and space used
Shows improvements over existing methods for specific α values

Abstract

The longest common subsequence (LCS) problem, consisting of finding an arbitrary LCS of given two strings, has been studied for a long time due to its many applications in fields. As a variant of this problem, we consider the problem of enumerating all LCSs. In LCS enumeration, there is a tradeoff between the delay time to find each LCS and the size of the space used to shorten it. For any positive constant α with α < 1, we propose anO(n2-α)-space algorithm that outputs all LCSs each in O(n1+α log2 n) time after an O(n2)-time preprocessing, where n is the length of the input strings.

Ask AI

Mark Helpful

Bookmark

Relay