Range Queries for Longest common subsequence

Question

General problem of Longest common Subsequence ( to be used as LCS hereafter) :-

Given two Strings, find the length of LCS present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.

For example:- “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. but “acb”, “age”... etc. are not.

We can use dynamic programming to find solution for this in O(nm) where n and m are length of string respectively. Here is the pseudocode for the same: -

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

However Now I have several queries of the form [L,R] and in each query i have to find length of LCS of string1 and substring of string2 ie.(s2[L] s2[L+1].....s2[R]).

For Example:-

s1= "aacdef"

s2= "aaxcef"

query [0,3]: - s1= "aacdef"

               s2= "aaxc"

               length of LCS of s1 and s2 = 3 (LCS = "aac")

query [2,5]: - s1= "aacdef"

               s2= "xcef"

               length of LCS of s1 and s2 = 3 (LCS = "cef")

One Brute force method is to simply run the general LCS solution every time a new query is asked. However if number of queries are large, its time complexity will become very large. So, can we do better than this?

Range Queries for Longest common subsequence

0 Answers