4
$\begingroup$

I want to know which is the best way to find the longest common subsequence of two strings

$\endgroup$
  • 1
    $\begingroup$ What method did you try to use, and why do you think it's wrong? $\endgroup$ – Yuval Filmus May 10 '13 at 2:53
  • $\begingroup$ @YuvalFilmus I used dynamic programming to find a string that is not a subsequence of A and another string that is not a subsequence of B and try to get something out of it. But my approach is wrong $\endgroup$ – user8105 May 10 '13 at 3:23
  • $\begingroup$ Just a clarification, do you want a subsequence, or substring? $\endgroup$ – Luke Mathieson May 10 '13 at 4:36
  • $\begingroup$ Wait! Your last edit totally changed the problem/question you are asking about. Don't do that. $\endgroup$ – D.W. May 10 '13 at 16:00
  • $\begingroup$ This link might help you.. ics.uci.edu/~eppstein/161/960229.html $\endgroup$ – Learner May 12 '13 at 14:18
1
$\begingroup$

You know the recipe for dynamic programming: define some subproblems, then show how to use solutions to smaller subproblems to help you solve larger subproblems. So, what you have tried as candidate subproblems?

Hint: When you have a dynamic programming problem that takes a string as input, what are some candidate ways to define subproblems? (Prefixes, suffices, substrings...) Now, how might you apply that general advice here?

I'm not going to spell out the full answer, as this sounds like homework, and to learn from homework, you need to struggle with it yourself.

$\endgroup$
  • $\begingroup$ Here OP talks about subsequences not substring, and seems he knows basics of DP. $\endgroup$ – user742 May 10 '13 at 9:26
  • $\begingroup$ @SaeedAmiri I tried to remove longest common subsequence in both and try out with the rest. But it was not the right approach $\endgroup$ – user8105 May 10 '13 at 10:59
  • $\begingroup$ @D.W. I know what dynamic programming is but I am not able think of the subproblem that is right for me $\endgroup$ – user8105 May 10 '13 at 11:03
  • 1
    $\begingroup$ @user8105 Don't expect us to solve the assignment for you. Continue thinking, and eventually you'll find the solution. $\endgroup$ – Yuval Filmus May 10 '13 at 13:53
  • $\begingroup$ @YuvalFilmus I have solved the problem $\endgroup$ – user8105 May 10 '13 at 14:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.