Find the longest common subsequence in two string for example
input1 : <m a n a g e r>
input2: <d a n g e r>
output : <a n g e r> which length is 5
the longest common subsequence is anger
any language is welcome least complex solution will be appreciated
A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences.
//output must be "aagr" or "nagr" or both of these
//output must be aaa
//output must be oo
4)bdrcve , bcvde
//output must be bcve
Can someone clarify how is longest common subsequence in the challange example
<m a n a g e r> and <d a n g e r> is <a n g e r>? There is no continuous substring "anger" in "manager"
The answer should have been <g e r>. What am i missing here?
The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences. The longest common subsequence problem is a classic computer science problem, the basis of data comparison programs such as the diff utility, and has applications in bioinformatics. It is also widely used by revision control systemssuch as Git for reconciling multiple changes made to a revision-controlled collection of files.
I made this best to understand to all what is lcs problem when the challenge is over I will mark a best answer to that code
If it is truly finding comman substrings, it should not allow another characters between subsequent members of substring...Then for "manager" and "danger" output should be "ger" only...some other examples try with your codes..
1) "loop" and "pool" -->"oo"
2)"ahopebhope" and "chopedhope" -->hope
3)"pqrs" and "srqp" --> no subsequence is matching
following code is giving the same outputs if matching substring length is more then 1