[Tutor] longest common substring

lina lina.lastname at gmail.com
Fri Nov 11 03:50:09 CET 2011


On Fri, Nov 11, 2011 at 1:21 AM, Peter Otten <__peter__ at web.de> wrote:
> lina wrote:
>
>> Hi,
>>
>> I tested the one from
>>
> http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring
>>
>> mainly:
>>
>> #!/usr/bin/python3
>>
>> a=['1','2','3','7']
>>
>> b=['2','3','7']
>>
>> 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]
>>
>>
>> if __name__=="__main__":
>>         print(LongestCommonSubstring(a,b))
>>
>> $ python3 LongestCommonSubstring.py
>> ['1', '2', '3']
>>
>> The results isn't right.
>
> That's not the code from the site you quote. You messed it up when you tried
> to convert it to Python 3 (look for the suspicious 8-space indent)
>
You are right.
also correct it to 4-space indention now. Thanks.
> Hint: the function doesn't contain anything specific to Python 2 or 3, apart
> from the xrange builtin. If you add the line
>
> xrange = range

Thanks, I did not realize I could substitute the xrange to range this way. cool.

>
> to your code the unaltered version will run in Python 3 -- and produce the
> correct result:
>
> $ cat longest_common_substring3.py
> xrange = range
>
> def LongestCommonSubstring(S1, S2):
>    M = [[0]*(1+len(S2)) for i in xrange(1+len(S1))]
>    longest, x_longest = 0, 0
>    for x in xrange(1,1+len(S1)):
>        for y in xrange(1,1+len(S2)):
>            if S1[x-1] == S2[y-1]:

I did not understand the code well, and the  if S1[x-1] == S2[y-1]:
was missing during I was typing ( I did not copy/paste, try to type to
enhance the learning)

>                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]
>
> if __name__ == "__main__":
>    a = ['1','2','3','7']
>    b = ['2','3','7']
>
>    print(LongestCommonSubstring(a, b))
> $ python3 longest_common_substring3.py
> ['2', '3', '7']
>
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
>


More information about the Tutor mailing list