Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

LLI_E_P_JI_O_K's blog

By LLI_E_P_JI_O_K, history, 22 months 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?

Read more »

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