[Tutor] longest common substring

[Peter Otten]

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