LLI_E_P_JI_O_K's blog

By LLI_E_P_JI_O_K, history, 6 years ago, translation, In English

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?

Full text and comments »

  • Vote: I like it
  • +26
  • Vote: I do not like it