"Progettare un algoritmo per trovare la sottosequenza comune più lunga tra due stringhe."
s1 = 'ABCDGH'
s2 = 'AEDFHR'

s1 = 'ABCDGH'
s2 = 'AEDFHR'
def LCS(s1, s2):
    m = len(s1)
    n = len(s2)

    # dichiarazione dell'array per memorizzare i valori dp
    L = [[None]*(n + 1) for _ in range(m + 1)]

    """I seguenti passaggi costruiscono L[m + 1][n + 1] dal basso verso l'alto
    Nota: L[i][j] contiene la lunghezza della LCS di X[0..i-1]
    e Y[0..j-1]"""
    for i in range(m + 1):
        # la riga precedente è tutta a zero,
        # poiché non è possibile creare alcuna sequenza comune utilizzandole
        for j in range(n + 1):
            # la prima colonna di tutte le righe è 0
            if i == 0 or j == 0 :
                L[i][j] = 0
            elif s1[i-1] == s2[j-1]:
                L[i][j] = L[i-1][j-1]+1
            else:
                L[i][j] = max(L[i-1][j] , L[i][j-1])

    # L[m][n] contiene la lunghezza della LCS di X[0..n-1] e Y[0..m-1]
    return L[m][n]