Prépa Code Connexion Inscription

Écrire une fonction plsc : int list -> int list -> int qui renvoie la longueur de la plus longue sous-suite commune à deux listes d'entiers.

Une sous-suite d'une liste est une liste obtenue en supprimant un certain nombre (éventuellement zéro) d'éléments, sans changer l'ordre des éléments restants. Attention : les éléments d'une sous-suite n'ont pas à être consécutifs dans la liste d'origine.

Par exemple, plsc [1; 2; 3; 4] [2; 4; 1; 3] = 2 : on peut trouver [2; 3] ou [1; 3] comme sous-suite commune de longueur 2, et on ne peut pas faire mieux.

Si une des listes est vide, la réponse est 0.

On pourra convertir les listes en tableaux pour accéder aux éléments en temps constant.