Optimized LCS for short sequence case

Revision en1, by LLI_E_P_JI_O_K, 2018-05-05 12:55:24

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?

Tags lcs, subsequence


  Rev. Lang. By When Δ Comment
en1 English LLI_E_P_JI_O_K 2018-05-05 12:55:24 714 Initial revision for English translation
ru1 Russian LLI_E_P_JI_O_K 2018-05-05 12:37:02 714 Первая редакция (опубликовано)