Home \ Seminars @ CITI \ Seminar Page | Login |
Representing Almost All Local Longest Common Subsequence Values { Wed, 27 May 2009, 14h00 } By: Luís Russo 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. Hosted by: Software Systems Location: DI seminars room |