#Q2
def est_sousChaine(ch, sch):
    j = 0
    for i in range(len(ch)):
        if ch[i] == sch[j]:
            j += 1
        if j == len(sch):
            return True
    return False

print( est_sousChaine("Bonjour", "osnur"))

#Q3
def est_commune(ch1, ch2, sch):
    return est_sousChaine(ch1, sch) and est_sousChaine(ch2, sch)
print( est_commune("bonsoir", "bonjour", "bon"))

#Q5
def lg_PlusLgueSuiteCommune( ch1, ch2 ) :
    n = len(ch1)
    m = len(ch2)

    if n ==0 or m==0 :
        return 0
    elif ch1[n-1]==ch2[m-1]:
        return 1 + lg_PlusLgueSuiteCommune( ch1[0:n-1], ch2[0:m-1])
    else : 
        return max ( lg_PlusLgueSuiteCommune( ch1, ch2[0:m-1]),
                         lg_PlusLgueSuiteCommune( ch1[0:n-1], ch2) )

print ( lg_PlusLgueSuiteCommune( "Bonjour", "onjbur")  )
print ( lg_PlusLgueSuiteCommune( "AATGCG", "TATTAGC") )
print ( lg_PlusLgueSuiteCommune( "Bonjour", "abba") )

#Q6
def PlusLgueSuiteCommune( ch1, ch2 ) :
    n = len(ch1)
    m = len(ch2)

    if n==0 or m==0 :
        return ""
    elif ch1[n-1]==ch2[m-1]:
        return   PlusLgueSuiteCommune( ch1[0:n-1], ch2[0:m-1]) + ch1[n-1]
    else : 
        sch1 =  PlusLgueSuiteCommune( ch1, ch2[0:m-1] )
        sch2 =  PlusLgueSuiteCommune( ch1[0:n-1], ch2 )
        if len(sch1) > len(sch2) : 
            return PlusLgueSuiteCommune( ch1, ch2[0:m-1])
        else : 
            return PlusLgueSuiteCommune( ch1[0:n-1], ch2)

print ( PlusLgueSuiteCommune( "Bonjour", "jus")  )
print ( "teste",PlusLgueSuiteCommune( "AATGCG", "TATTAGC") )
print ( PlusLgueSuiteCommune( "Bonjour", "abba") )

# Q7 Programmation dynamique - avec l'utilisation d'un dictionnaire
def PlusLgueSuiteCommune_mem( ch1, ch2, mem) :
    n = len(ch1)
    m = len(ch2)
    if n ==0 or m==0 :
        return ""
    elif (ch1,ch2) in mem : #La + longue suite commune a deja été memorisée?
        return   mem[(ch1,ch2)]
    elif ch1[n-1]==ch2[m-1]:
        mem[(ch1,ch2)] = PlusLgueSuiteCommune_mem( ch1[0:n-1], ch2[0:m-1],mem) + ch1[n-1]
    else : 
        sch1 =  PlusLgueSuiteCommune_mem( ch1, ch2[0:m-1],mem )
        sch2 =  PlusLgueSuiteCommune_mem( ch1[0:n-1], ch2,mem )
        if len(sch1) > len(sch2) : 
            mem[(ch1,ch2)] = sch1
        else:
            mem[(ch1,ch2)] = sch2
    #print( mem)
    return   mem[(ch1,ch2)]
mem = {}
print ( PlusLgueSuiteCommune_mem( "Bonjour", "onjbur", mem)  )
print ( PlusLgueSuiteCommune_mem( "AATGCG", "TATTAGC",mem) )
print ( PlusLgueSuiteCommune_mem( "Bonjour", "abba",mem) )

#Q8
def PlusLgueSuiteCommune_Iter (ch1,ch2):
    n = len(ch1)
    m = len(ch2)
    L = [[0 for j in range (m+1)] for i in range (n+1)]
    for ligne in range (1,n+1):
        for colonne in range (1,m+1):
            if ch1[ligne -1]== ch2[colonne -1]:
                L[ ligne ][ colonne ] = 1 + L[ligne -1][ colonne -1]
            else:
                L[ ligne ][ colonne ] = max(L[ ligne ][ colonne -1] ,L[ligne -1][ colonne])
    return L
print ( PlusLgueSuiteCommune_Iter( "Bonjour", "onjbur") )