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?
