[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