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

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.