A data structure for substring-substring LCS length queries

The longest common subsequence (LCS) length of two strings is used as one of the most fundamental metrics measuring the similarity between the strings. To find out the local structures common to the strings under this similarity metric, we need a fast calculation of the LCS length of any pair of substrings of the two strings. For supporting such queries, it makes sense to preprocess the two strings in a quadratic time, because it takes about the same amount of time to compute the LCS length of the entire strings from scratch. We propose a quadratic-time constructible data structure that supports sublinear-time queries of the LCS length for any pair of substrings. The query time is O(llog^1+ϵ⁡l), where ϵ is a positive constant arbitrarily small and l is the sum of the substring lengths.