[Tutor] longest common substring

Walter Prins wprins at gmail.com
Thu Nov 10 18:23:58 CET 2011


On 10 November 2011 16:23, lina <lina.lastname at gmail.com> wrote:

> def LongestCommonSubstring(S1, S2):
>        M = [[0]*(1+len(S2)) for i in range(1+len(S1))]
>        longest, x_longest = 0, 0
>        for x in range(1,1+len(S1)):
>                for y in range(1,1+len(S2)):
>                        M[x][y] = M[x-1][y-1]+1
>                        if M[x][y] > longest:
>                                longest = M[x][y]
>                                x_longest = x
>                        else:
>                                M[x][y] = 0
>        return S1[x_longest-longest:x_longest]

This is not the same as the implementation given on wikibooks.... Have you
tried reverting your changes and using the coe that was given on the site
exactly as is?  (I assume not, and if so, why not?)

(Specifically, I notice most the likely culprit is a missing if statement
just below the "for y in range..." line that's been deleted....)

> The results isn't right.

Yes.  You appear to have introduced a bug by not using the same code as
what was given on the wiki page.  (Why did you modify the code and then
when the modified code didn't work assume the original solution was broken
instead of checking first and/or suspecting that your changes may have
broken it?)

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20111110/09b28f36/attachment.html>

More information about the Tutor mailing list