Prépa Code Connexion Inscription

Écrire une fonction plsc : string -> string -> int qui renvoie la longueur de la plus longue sous-suite commune à deux chaînes de caractères.

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

Par exemple, plsc "abcd" "bdac" = 2 : on peut trouver "bc" ou "ad" comme sous-suite commune de longueur 2, et on ne peut pas faire mieux.

Si une des chaînes est vide, la réponse est 0.

On rappelle que String.length s renvoie la longueur de s et que s.[i] renvoie le caractère d'indice i.