# [Tutor] longest common substring

Peter Otten __peter__ at web.de
Thu Nov 10 18:21:54 CET 2011

```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)

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

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]:
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']

```