Detail

Representing Almost All Local Longest Common Subsequence Values

In this talk we consider the problem of representing the values of the
local Longest Common Subsequences (LCS), of two strings. In a recent paper
Tiskin proposed a way to represent the size of the LCS’s of one string against
all the substrings of another string and all the suffixes of one
against all the prefixes of the other string. His representation
requires only O((m + n) log(m + n))
bits and obtains any of the O((m + n)^2 ) possible values with only O(log(m +
n)/ log log(m + n)) operations, assuming m and n are the size of the
strings. This
result exposed regularities that occur when trying to represent all these values
together instead of individually. We take this approach one step
further and propose a way to represent the LCS values of every prefix of one
string against every substring of another string. This representation
requires only
mn + o(m(m + n)) bits and returns each of the O(m(m + n)^2 ) possible values
in O((log(m + n) log log(m + n))^2 ) time. Simply iterating Tiskin’s
representation
would be faster by a factor of O(log m(log log m)^3 ) but it would require more
space, O(m(m + n) log(m + n)) bits. In fact our approach offers a
range of inbetween space time trade-offs and presents new insights
into the framework presented by Tiskin.