There is a well known algorithm of searching the largest common subsequence of two sequences with lengths *N* and *M* in *O*(*N*·*M*) time: Link to the algorithm description

But I've recently heard there is some technique that allows to reduce time if one of the sequences is short enough and works in *O*(*min*(*N*, *M*)^{2} + *max*(*N*, *M*)). Does anybody know how to do it?

Seems pretty obvious:

dp_{i, j}stores the leastksuch that LCS ofi-th prefix of small sequence andk-th prefix of large sequence isj.Wow, definitely, it's quite easy, thanks a lot! :)

For moving to the state

dp[i+ 1][j+ 1] we need to find the first entry of elements[i+ 1] in big sequence starting from thedp[i][j] + 1 position, how to implement it inO(1) if the alphabet size is big? Won't there be an additionallog2(max(N,M)) in the time estimation?(Kind of overkill probably.)

Let

nbe the length of longer sequence andmbe the length of shorter sequence.First thing we do is deleting all characters from longer sequence that don't apper in shorter sequence in

O(n+m) time using hashmap. Now, there are onlymsymbols left in the "effective alphabet". Also this construction allows us to think that alphabet is just [0,m- 1] (this part seems to be unnecessary if alphabet is something like [0,n- 1], but should reduce hidden constant if alphabet is big enough).One thing we may notice is that iterating over (

i,j) in any kind of lexicographical order is unnecessary: we may iterate over them in order of increasing`dp[i][j]`

, which will turn out to be more conventient. This way all dp recalculations will still happen in valid order.To achieve this, we will use

n+ 1 queues: queue numberkwill hold all (i,j) such that`dp[i][j] = k`

. Then we can just iteratekfrom 0 ton- 1, consider all pairs fromk-th queue (there are two types of transitions`(i, j, k) -> (i + 1, j, k)`

just adds new pair in current queue for later consideration, and`(i, j, k) -> (i + 1, j + 1, nk > k)`

is interesting, but affects only later queues).The difference between this and naive update order is that now queries "find first symbol equal to

cin longer string from positionpinclusive" happen in increasing order ofp. Suppose that we have an array of answers for all such queries for positionp. Transition top+ 1 is simple, because only for one symbol answer changes — exactly for symbol atp-th position of longer string. And for it, answer changes to next position of this symbol in longer string. Next positions of each symbol can be precalculated inO(n+m), so we can answer this queries inO(1) after some precalculations, becauseponly increases.TL;DR: process states in order of increasing values of

`dp[i][j]`

, this way start of the query segments always move right, which makes recalculating answers inO(1) possible.Ok, thanks a lot, interesting approach :)

Not seems to be an "overkill". Additional

log2(max(N,M)) can seriously influence to the time.