Exercice 3

Sous-mots

Soient 2 mots x et y supposés déclarés en C par:

char x[100]; char y[100];

1)Écrire en C une fonction qui teste si x est un sous-mot de y

2)Ecrire en C une fonction qui calcule lsc(x,y),la longueur maximale des sous-mots communs à x et y

3)Calculer la table Tx,y relative aux mots x = agctga et y = cagatcagag et définie par :

Tx,y[i,j] = lsc(x[0]x[1]...x[i-1],y[0]y[1]...y[j-1])

ou i = 0,1...|x| et j= 0,1...|y|.(Pour i = 0 on convient x[0]x[1]...x[i-1] est le sous mot vide; meme convention avec y[0]y[1]...y[j-1] quand j = 0)

4)Quels sont les plus longs sous-mots communs à agctga et cagatcagag?.
Indiquer comment calculer un sous mot commun à x et y et de longeur lsc(x,y) à partir de la table Tx,y[/i]

*** message déplacé ***