Chaînes de caractères

Le but de cet série d'exercice est d'étudier les modifications d'une chaîne de caractères.

Sous-séquence

Soient deux chaînes de caractères $S_1$ et $S_2$. On dit que $S_2$ est une sous-séquence de $S_1$ si il existe une fonction strictement croissante

$$ f : {0,\ldots, len(S_2)-1} \longrightarrow {0,\ldots, len(S_1)-1} $$

Telle que $S_1[f(j)] = S_2[ j]$ pour tout $j$ de ${0,\ldots, len(S_2)-1}$.

Proposez, prouvez et donnez la complexité d'un algorithme qui détermine si $S_2$ est une sous-séquence de $S_1$.

Sous-mot

Soient deux chaînes de caractères $S_1$ et $S_2$. On dit que $S_2$ est un sous-mot de $S_1$ s'il existe un indice $i$ tel que $S_2[j] = S_1[i + j]$ pour tout $j$ de $0$ à $len(S_2) - 1$.

Permutation circulaire

Étant donné un liste $L$ de longueur $n$ et un entier $k$, le problème est de transformer $L$ par permutation circulaire en décalant (circulairement) tous les éléments de $L$ de $k$ places. Par exemple, avec $L = \text{LongtempsJeMeSuisCouchéDeBonneHeure}$ et $k = 4$, on obtient $L' = \text{eureLongtempsJeMeSuisCouchéDeBonneH}$.

On veut maintenant faire une permutation circulaire sur site, ie. sans utiliser plus que $O(1)$ place mémoire supplémentaire (il arrive (par exemple quand on étudie le génome) que $n$ soit très grand). Il faut pour cela remarquer que permuter circulairement $L$ revient à prendre les $k$ dernières lettres de $L$ et à les mettre en tête. On note $L^R$ la liste $L$ renversée (par exemple, si $L =\text{Couché}$, $L^R = \text{éhcuoC}$).