I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by solving LCS for bit-strings we can also solve LCS with an arbitrary (but finite) alphabet cardinal.

It seems reasonable for me that such a reduction exists (based on the complexity of algorithms for various versions of the problem), however, I couldn't find something like that.

  • $\begingroup$ I think the algorithm doesn't care about the alphabet. $\endgroup$ – Raphael Jun 7 '16 at 20:18
  • $\begingroup$ The algorithm does not care, however, I am working on another problem regarding LCS, and I can solve it for the binary version. I need the reduction to generalize my solution! On the other hand, my own problem aside, this reduction seems interesting on its own (at least for me!) @Raphael $\endgroup$ – Nima Jun 8 '16 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.