################################################################################
################################################################################
#   PLSC
################################################################################
################################################################################

import numpy as np
from collections import deque

################################################################################
#   
################################################################################

def PLSC_rec(X,Y):
    """PLSC_rec(X:str,Y:str)->str
    Calcul d'une plus longue sous-suite commune à X,Y
    de manière descendante sans mémoïsation"""
    # A COMPLETER
    pass

print("Approche descendante sans mémoïsation")
print(PLSC_rec("matrice","application"))
print()

################################################################################
#   
################################################################################


def PLSC_memo(X,Y):
    """PLSC_memo(X:str,Y:str)->str
    Calcul d'une plus longue sous-suite commune à X,Y
    de manière descendante avec mémoïsation"""
    # A COMPLETER
    pass


print("Approche descendante avec mémoïsation")
print(PLSC_memo("matrice","application"))
print()

################################################################################
#   
################################################################################


def C_tab(X,Y):
    """C_tab(X:int,Y:int)->list
    Calcul de la matrice C des tailles des plus longues
    sous-suites communes aux chaînes extraites de X et Y"""
    n,m=len(X),len(Y)
    tab=[[0]*(m+1) for i in range(n+1)]
    # A COMPLETER
    pass


print("Matrice de l'approche ascendante")
print(np.array(C_tab("matrice","application")))
print()


################################################################################
#   
################################################################################

def PLSC_asc(X,Y):
    """PLSC_asc(X:str,Y:str)->str
    Calcul d'une plus longue sous-suite commune à X,Y
    de manière ascendante"""
    n,m=len(X),len(Y)
    tab=C_tab(X,Y)
    # A COMPLETER
    pass


print("Approche ascendante - une PLSC")
print(PLSC_asc("matrice","application"))
print()

################################################################################
#   
################################################################################


def PLSC_all(X,Y):
    """PLSC_all(X:str,Y:str)->list
    Calcul de toutes les plus longues sous-suites communes à X,Y"""
    n,m=len(X),len(Y)
    tab=C_tab(X,Y)
    file_PLSC=deque()
    res=[]
    file_PLSC.append(((n,m),""))
    # A COMPLETER
    pass

print("Approche ascendante - toutes les PLSC")
print(PLSC_all("matrice","application"))
print()