[Tutor] Algorithm for sequence matching
Walter Prins
wprins at gmail.com
Sun Jul 3 00:59:42 CEST 2011
Just to clarify further:
On 2 July 2011 23:46, Walter Prins <wprins at gmail.com> wrote:
> On 2 July 2011 21:30, ANKUR AGGARWAL <coolankur2006 at gmail.com> wrote:
>
>> Example : list a accepts some say 'm' numbers. list b accept says 'n'
>> numbers. I want to look for the largest same sequence between the two list
>> and then display it. I tried out but failed to do so.
>> Say A=[11,23,45,21,63,56,78,32]
>> B=[56,78,11,23,45,21,111,234,56543]
>>
>> There are two similar sequence matching over here [11,23] and
>> [11,23,45,21] i want to display second sequence because its larger in
>> number. Plz help
>>
>
> OK, so what if A = [1,4,2,7,4,6] and B = [4,9,10,11,12,14,17,4]? Would you
> consider [4,4] a valid answer to your question? It is a common subsequence,
> albeit not of concescutive elements?
>
There is a difference between a sub*sequence* and a sub*string*. Strictly
speaking, a *subsquence* is a sequence that can be derived from another
sequence by deleting some of the elements from the other sequence. The
result thus retains the ordering from the original but the elements need not
have been consecutive elements. A *substring* on the other hand implies
consecutive elements. I'm trying to make sure I understand your question,
and whether you're really after the longest common subsequence (LCS) or
longest common substring. My question above thus are trying to establish
which of the two cases you're really after. Obviously the answer will be
different depending on what you really want.
Regards
Walter
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20110702/33722cc4/attachment-0001.html>
More information about the Tutor
mailing list