Séquences et chaînes de caractères

Une séquence est une suite finie de symboles : une chaîne de caractères, un brin d'ADN (symboles A, C, G, T), un fichier vu comme une suite de lignes… Les problèmes de ce chapitre ont un point commun : les sous-problèmes naturels portent sur les préfixes des séquences. Le $p$-préfixe de $T=t_0{t}_1\dots t_{m-1}$ est $T[0:p]=t_0\dots t_{p-1}$ ; le $0$-préfixe est la séquence vide, le $m$-préfixe est $T$ elle-même.

En Java, on représente les séquences par des chaînes (String) :

• S.length() est la longueur de la chaîne ;
• S.charAt(i) est le caractère d'indice $i$ ;
• S.substring(i,j) est la sous-chaîne $S[i:j]$ ; en particulier S.substring(0,p) est le $p$-préfixe ;
• S1 + S2 est la concaténation : "bon" + "jour" vaut "bonjour".

8.1 Plus longue sous-séquence commune

L'énumération exhaustive est hors de question : une séquence de longueur $m$ a $2^m$ sous-séquences.

8.1.1 Supposons le problème résolu

Soient $T$ et $U$ de longueurs $m$ et $n$, et $S$ une plsc à $T$ et $U$, de longueur $l(m,n)$. Regardons les derniers symboles $t_{m-1}$ et $u_{n-1}$. Il n'y a que quatre possibilités :

• $t_{m-1}=u_{n-1}$. On peut toujours supposer que ce symbole commun termine $S$ (sinon, l'ajouter à la fin d'une plsc des préfixes donnerait une sc plus longue). Le reste de $S$ est une plsc à $T[0:m-1]$ et $U[0:n-1]$ : $l(m,n)=1+l(m-1,n-1)$.
• $t_{m-1}\ne u_{n-1}$ et aucun des deux n'est le dernier symbole de $S$ : $S$ est une plsc aux deux séquences privées de leur dernier symbole, $l(m,n)=l(m-1,n-1)$.
• $t_{m-1}\ne u_{n-1}$ et $t_{m-1}$ n'est pas le dernier symbole de $S$ : on peut retirer $t_{m-1}$ de $T$ sans rien perdre, $l(m,n)=l(m-1,n)$. (Et $u_{n-1}$ ? Peu importe : il peut être, ou ne pas être, le dernier symbole de $S$.)
• $t_{m-1}\ne u_{n-1}$ et $u_{n-1}$ n'est pas le dernier symbole de $S$ : symétriquement, $l(m,n)=l(m,n-1)$.

Si les derniers symboles sont différents, l'un des deux au moins n'est pas le dernier symbole de $S$ : on est dans le cas B, C ou D, et $l(m,n)=\max \{l(m-1,n-1),l(m-1,n),l(m,n-1)\}$. Or une sc aux préfixes $T[0:m-1]$ et $U[0:n-1]$ est aussi une sc à $T[0:m-1]$ et $U$ : $l(m-1,n-1)\le l(m-1,n)$. Le cas B est donc inutile, et il reste deux cas.

On généralise aux $p$- et $q$-préfixes : $l(p,q)$ est la longueur d'une plsc à $T[0:p]$ et $U[0:q]$. Si l'un des préfixes est vide, la seule sc est la séquence vide.