TP 5 : Chaînes de caractères

Recherche de sous-mots¶

Exercice

1. Écrire une fonction bool prefix(const char*, const char*) déterminant si une chaîne de caractères commence par un certain mot. Par exemple, prefix("info", "informatique") doit renvoyer true.
2. Écrire une fonction bool subword(const char*, const char*) déterminant si un mot apparaît (de façon consécutive) dans une chaîne de caractères. Par exemple, subword("for", "informatique") renvoie true.

Solution

In [15]:

// 1.
bool prefix(const char* mot, const char* s) { // détermine si mot est préfixe de s, en supposant strlen(mot) <= strlen(s)
    for(int i = 0; mot[i] != '\0'; i++)
        if(mot[i] != s[i])
            return false;
    return true;
}

prefix("info", "informatique") && !prefix("nfo", "informatique")

// 1. bool prefix(const char* mot, const char* s) { // détermine si mot est préfixe de s, en supposant strlen(mot) <= strlen(s) for(int i = 0; mot[i] != '\0'; i++) if(mot[i] != s[i]) return false; return true; } prefix("info", "informatique") && !prefix("nfo", "informatique")

Out[15]:

true

Solution

In [16]:

// 2.
bool subword(const char* mot, const char* s) { // détermine si mot est un sous-mot de s
    int n = strlen(s) - strlen(mot) + 1; // on fait attention à ne pas dépasser
    for(int i = 0; i < n; i++)
        if(prefix(mot, &s[i]))
            return true;
    return false;
}

subword("for", "informatique") && !subword("nft", "informatique")

// 2. bool subword(const char* mot, const char* s) { // détermine si mot est un sous-mot de s int n = strlen(s) - strlen(mot) + 1; // on fait attention à ne pas dépasser for(int i = 0; i < n; i++) if(prefix(mot, &s[i])) return true; return false; } subword("for", "informatique") && !subword("nft", "informatique")

Out[16]:

true

Anagramme¶

Exercice

Écrire une fonction bool anagramme(const char*, const char*) déterminant si deux chaînes de caractères sont des anagrammes, c'est-à-dire si l'une peut être obtenue en permutant les lettres de l'autre (en changeant la position des lettres).
Par exemple, anagramme("casser", "sacres") doit renvoyer true.
On supposera que tous les caractères sont des lettres (de a à z) et on demande un algorithme en complexité linéaire.

Solution

In [17]:

bool anagramme(const char* s1, const char* s2) {
    int tab[26] = {0}; // va compter le nombre de lettres de s1 - nombre de lettres de s2
    for(int i = 0; s1[i] != '\0'; i++)
        tab[s1[i] - 'a']++;
    for(int i = 0; s2[i] != '\0'; i++)
        tab[s2[i] - 'a']--;
    for(int i = 0; i < 26; i++)
        if(tab[i] != 0)
            return false;
    return true;
}

anagramme("casser", "sacres") && !anagramme("casier", "recase")

bool anagramme(const char* s1, const char* s2) { int tab[26] = {0}; // va compter le nombre de lettres de s1 - nombre de lettres de s2 for(int i = 0; s1[i] != '\0'; i++) tab[s1[i] - 'a']++; for(int i = 0; s2[i] != '\0'; i++) tab[s2[i] - 'a']--; for(int i = 0; i < 26; i++) if(tab[i] != 0) return false; return true; } anagramme("casser", "sacres") && !anagramme("casier", "recase")

Out[17]:

true

Table de hachage sur des chaînes de caractères¶

On veut implémenter une table de hachage dont les clés sont des chaînes de caractères (qu'on supposera contenir seulement des lettres de a à z, donc pas d'espace) et les valeurs sont des entiers. On va donc stocker les valeurs dans un tableau t de taille $n$ et on a besoin d'une fonction de hachage h qui à une chaîne de caractères s associe un indice de t.
Pour que les calculs soient plus simples, on commence par définir le haché d'un caractère par sa position dans l'ordre alphabétique (en commençant à 1). Par exemple, le haché de 'a' est 1, le haché de 'b' est 2...

Exercice

Écrire une fonction int hash(char) renvoyant le haché d'une lettre (entre 'a' et 'z').

Solution

In [3]:

int hash(char c) {
    return c - 'a' + 1; // conversion implicite de c et `a` en int
}

hash('b')

int hash(char c) { return c - 'a' + 1; // conversion implicite de c et `a` en int } hash('b')

Out[3]:

2

Soit $p$ un nombre supérieur ou égale au nombre de caractères (on choisit souvent $p$ premier pour que les valeurs de la fonction de hachage soient bien distribuées). Si $s$ est une chaîne de caractères de taille $m$, on définit : $$h(s) = \sum_{i = 0}^{m - 1} \text{hash}(s[i]) \times p^i \mod n$$ Remarque : Le modulo est appliqué sur tous les termes de la somme.

Exercice

Écrire une fonction int h(const char*, int, int) telle que h(s, p, n) renvoie la valeur de $h(s)$ ci-dessus. On évitera de faire plusieurs calculs de puissance et on appliquera le modulo sur chaque terme de la somme (pour éviter de faire des calculs sur des entiers trop grands).

Solution

In [4]:

int h(const char* s, int p, int n) {
    int somme = 0;
    int puiss = 1; // variable pour stocker les puissances de p
    for(int i = 0; s[i] != '\0'; i++) {
        somme = (somme + hash(s[i])*p) % n;
        puiss = (puiss*p) % n;
    }
    return somme;
}

h("helloworld", 31, 11867)  // exemple de codage

int h(const char* s, int p, int n) { int somme = 0; int puiss = 1; // variable pour stocker les puissances de p for(int i = 0; s[i] != '\0'; i++) { somme = (somme + hash(s[i])*p) % n; puiss = (puiss*p) % n; } return somme; } h("helloworld", 31, 11867) // exemple de codage

Out[4]:

3844

Dans la suite, on prend $p = 31$ et $n = 11867$ (un nombre premier assez grand).

Exercice

Écrire une fonction void add(const char*, int, int*) telle que add(k, v, t) ajoute une clé k avec la valeur v dans t.
Remarque : Si t contenait déjà une valeur dans $h(k)$, add ecrase cette ancienne valeur, ce qui n'est normalement pas souhaitable.

Solution

In [5]:

void add(const char* k, int v, int* t) {
    t[h(k, 31, 11867)] = v;
}

void add(const char* k, int v, int* t) { t[h(k, 31, 11867)] = v; }

Exercice

Écrire une fonction int get(const char*, int*) telle que get(k, t) renvoyant la valeur associée à k dans t.

Solution

In [6]:

int get(const char* k, int* t) {
    return t[h(k, 31, 11867)];
}

int get(const char* k, int* t) { return t[h(k, 31, 11867)]; }

Exercice

Écrire une fonction char* sub(const char*, int, int) telle que sub(s, i, n) renvoie un sous-mot de s de n caractères et commençant en i. Par exemple, sub("informatique", 2, 3) doit renvoyer un pointeur vers "for".

Solution

In [7]:

char* sub(const char* s, int i, int n) {
    char* res = (char*)malloc((n+1)*sizeof(char));
    for(int k = 0; k < n; k++)
        res[k] = s[k + i];
    res[n] = '\0'; // ne pas oublier le symbole de fin de chaîne de caractères
    return res;
}

sub("informatique", 2, 3)

char* sub(const char* s, int i, int n) { char* res = (char*)malloc((n+1)*sizeof(char)); for(int k = 0; k < n; k++) res[k] = s[k + i]; res[n] = '\0'; // ne pas oublier le symbole de fin de chaîne de caractères return res; } sub("informatique", 2, 3)

Out[7]:

"for"

Exercice

Écrire une fonction char* most_frequent_word(const char*, int) telle que most_frequent_word(s, l) renvoie le mot de longueur l apparaissant le plus souvent dans s. Par exemple, most_frequent_word("abcbcaabc", 2) doit renvoyer bc (qui apparaît 3 fois).

Solution

In [8]:

char* most_frequent_word(const char* s, int l) {
    int t[11867] = { 0 };
    int n = strlen(s);
    int max_freq = 0;
    char* max_word = NULL;
    for(int i = 0; i < n - l + 1; i++) {
        char* subword = sub(s, i, l);
        int freq = get(subword, t);
        freq++;
        add(subword, freq, t);
        if(freq > max_freq) {
            max_freq = freq;
            if(max_word)
                free(max_word);
            max_word = subword;
        }
        else
            free(subword);
    }
    return max_word;   
}

most_frequent_word("abcbcaabc", 2)

char* most_frequent_word(const char* s, int l) { int t[11867] = { 0 }; int n = strlen(s); int max_freq = 0; char* max_word = NULL; for(int i = 0; i < n - l + 1; i++) { char* subword = sub(s, i, l); int freq = get(subword, t); freq++; add(subword, freq, t); if(freq > max_freq) { max_freq = freq; if(max_word) free(max_word); max_word = subword; } else free(subword); } return max_word; } most_frequent_word("abcbcaabc", 2)

Out[8]:

"bc"

Exercice

Réécrire add et get en utilisant une liste chaînée dans chaque case du tableau t (comme ce que l'on a fait en cours sur les tables de hachage en OCaml). t sera donc de type list** (un tableau dont chaque élément est une list*).