Greedy String Tiling In Python

I am trying to learn greedy string tiling in algorithm I have two lists as follows: a=['a','b','c','d','e','f'] b=['d','e','a','b','c','f'] i would like to retrieve c=['a','b','c'

Solution 1:

The following codes can solve the problem. A minlength is added to make sure the substr >= minlength.

• maxsub is used to find the longest substr and return its index in string a.
• markit.a is used to mark the char position found before in string a.
• while loop is used to find all the substr (len>=minlength)

^

#! /usr/bin/env python
a=['a','b','c','d','e','f']
b=['d','e','a','b','c','f']

a = ['1','2','3','4','5','6','7','8','9','1','3']
b = ['3','4','5','2','1','7','8','9','1']

defgct(a,b,minlength=2):
    iflen(a) == 0orlen(b) == 0:
        return []
    # if py>3.0, nonlocal is betterclassmarkit:
        a=[0]
        minlen=2
    markit.a=[0]*len(a)
    markit.minlen=minlength

    #output char index
    out=[]

    # To find the max length substr (index)# apos is the position of a[0] in origin stringdefmaxsub(a,b,apos=0,lennow=0):
        if (len(a) == 0orlen(b) == 0):
            return []
        if (a[0]==b[0] and markit.a[apos]!=1 ):
            return [apos]+maxsub(a[1:],b[1:],apos+1,lennow=lennow+1)
        elif (a[0]!=b[0] and lennow>0):
            return []
        returnmax(maxsub(a, b[1:],apos), maxsub(a[1:], b,apos+1), key=len)
    whileTrue:
        findmax=maxsub(a,b,0,0)
        if (len(findmax)<markit.minlen):
            breakelse:
            for i in findmax:
                markit.a[i]=1
            out+=findmax
    return [ a[i] for i in out]

print gct(a,b)
>> ['a', 'b', 'c', 'd', 'e']
>> ['7', '8', '9', '1', '3', '4', '5']
print gct(a,b,3)
>> ['a', 'b', 'c']
>> ['7', '8', '9', '1', '3', '4', '5']