[Tutor] longest common substring
lina
lina.lastname at gmail.com
Thu Nov 10 17:23:53 CET 2011
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.
Thanks for your suggestions and comments,
Best regards,
More information about the Tutor
mailing list