Salut,
J'aurais besoin d'aide pour les 3 exercices suivants.
Merci d'avance à ceux qui m'aideront.


Exercice 1
Tri de suffixe
On considère une table de caractères,y,de dimension n.Le but de cet exercice est de calculer la table Pos de dimension n pour laquelle  

y[Pos[0]..n-1]<y[Pos[1]..n-1]<....<y[Pos[n-1]..n-1]

ou y[i...n-1] = yy[i+1]...y[n-1] désigne le suffixe de y qui est à la position i.
La table fournit ainsi les suffixes non vides de y en ordre croissant (pour l'ordre lexicographique).

1)Ecrire en C le code de la fonction strcmp de prototype
int strcmp(const char *s, const char *t);

2)Ecrire en C une fonction d'en-tete
int Partage(int d, int f, int p)  qui appliquée aux suffixes dont les positions sont Pos[d], Pos[d+1], ..., Pos[f] et au pivot y[Pos[p]...n-1] = z (d p f), effectue le "partage" des suffixes considérés selon le pivot (en modifiant Pos) et produit le plus petit indice k (d k f) pour lequel y[Pos[k]...n-1] = z

3)Ecrire un algorithme de classement des suffixes de y qui produit la table Pos en utilisant la fonction de partage du 2. Quelle table Pos obtient-on avec y = "abracadabra" ?

4)Donnez une majoration asymptotique des temps d'execution de  
Partage(d,f,p)  et de l'algorithme de classement. Quel peut etre son temps moyen d'éxécution en supposant que le temps moyen pour comparer 2 suffixes est O(logn)[/b]