Les tableaux et les chaînes de caractères constituent des structures de données fondamentales. Cet article explore leurs principes algorithmiques et applications pratiques en C et C++.

Recherche dans les Chaînes (String Matching)

Étant donné une chaîne source et une chaîne cible, localiser l'occurrence initiale de la cible dans la source.

Algorithme Force Brute

Cette méthode compare systématiquement chaque position potentielle de la source avec la cible. La complexité temporelle est O(n*m) où n et m sont les longueurs des chaînes.

char* rechercherSousChaine(const char *texte, const char *motif) { if (motif == '\0') return (char)texte;

const char *debutTexte = texte;

while (*texte != '\0') {
    const char *positionTexte = texte;
    const char *positionMotif = motif;
    
    while (*positionTexte != '\0' && *positionMotif != '\0' && 
           *positionTexte == *positionMotif) {
        positionTexte++;
        positionMotif++;
    }
    
    if (*positionMotif == '\0') return (char*)debutTexte;
    
    texte = debutTexte + 1;
    debutTexte = texte;
}
return NULL;

}

</div>### Algorithme Rabin-Karp

Cette technique utilise le hachage pour une comparaison plus efficace. Elle calcule un hash pour chaque sous-chaîne de même longueur que la cible et le compare avec le hash de la cible. La complexité moyenne est O(n+m).

<div>```

#include <string>
#include <iostream>
#include <functional>

size_t rechercheRabinKarp(const std::string &texte, const std::string &motif)
{
    std::hash<:string> fonctionHash;
    
    size_t hashMotif = fonctionHash(motif);
    size_t longueurMotif = motif.length();
    
    for (size_t i = 0; i <= texte.length() - longueurMotif; ++i) {
        std::string sousChaine = texte.substr(i, longueurMotif);
        if (fonctionHash(sousChaine) == hashMotif) {
            if (sousChaine == motif) return i;
        }
    }
    return std::string::npos;
}
</:string></functional></iostream></string>

En C/C++, la mémoire peut être allouée sur la pile (stack) ou le tas (heap).

// Allocation sur la pile int tableauLocal[100];

// Allocation sur le tas int *tableauDynamique = new int[100]; // Libération nécessaire delete[] tableauDynamique;

</div>### Tableaux Bidimensionnels

<div>```

// Création sur le tas
int **matrice = new int*[lignes];
for (int i = 0; i < lignes; ++i) {
    matrice[i] = new int[colonnes];
}

// Libération
for (int i = 0; i < lignes; ++i) {
    delete[] matrice[i];
}
delete[] matrice;

Les tables de hachage sont essentielles pour les recherches rapides par clé. En C++, on peut utiliser std::unordered_map pour une complexité moyenne O(1) en insetrion, suppression et recherche.

Unicité des Caractères

Pour vérifier si tous les caractères d'une chaîne sont uniques, on peut utiliser un tableau de booléens ou un bitset.

#include #include

bool caracteresUniques(const std::string &chaine) { std::bitset<256> marqueurs;

for (char caractere : chaine) {
    unsigned int index = static_cast<unsigned int="">(caractere);
    if (marqueurs.test(index)) return false;
    marqueurs.set(index);
}
return true;

}

</div>### Vérification de Permutations

Deux chaînes sont des permutatoins si chaque caractère apparaît le même nombre de fois dans chacune.

<div>```

#include <unordered_map>
#include <string>

bool sontPermutations(const std::string &s1, const std::string &s2)
{
    if (s1.length() != s2.length()) return false;
    
    std::unordered_map<char int=""> compteur1;
    std::unordered_map<char int=""> compteur2;
    
    for (char c : s1) compteur1[c]++;
    for (char c : s2) compteur2[c]++;
    
    return compteur1 == compteur2;
}
</char></char></string></unordered_map>

Suppression d'Éléments

Supprimer toutes les occurrences d'une valeur donnée d'un vecteur.

#include

template void supprimerElements(std::vector &vec, const T &valeur) { auto it = std::remove(vec.begin(), vec.end(), valeur); vec.erase(it, vec.end()); }

</div>### Fusion de Tableaux Triés

Fusionner deux tableaux triés en un seul tableau trié.

<div>```

#include <vector>

std::vector<int> fusionnerTableauxTries(const std::vector<int> &a, 
                                       const std::vector<int> &b)
{
    std::vector<int> resultat;
    size_t i = 0, j = 0;
    
    while (i < a.size() && j < b.size()) {
        if (a[i] <= b[j]) {
            resultat.push_back(a[i++]);
        } else {
            resultat.push_back(b[j++]);
        }
    }
    
    while (i < a.size()) resultat.push_back(a[i++]);
    while (j < b.size()) resultat.push_back(b[j++]);
    
    return resultat;
}
</int></int></int></int></vector>

En C, les chaînes sont des tableaux de caractères terminés par '\0'. Les fonctions standard incluent strlen, strcpy, strcmp.

En C++, la classe std::string offre des méthodes comme find, substr, erase et surcharge les opérateurs courants.

Remplacement d'Espaces

Remplacer tous les espaces par "%20" dans une chaîne.

#include

std::string remplacerEspaces(const std::string &texte) { std::string resultat;

for (char caractere : texte) {
    if (caractere == ' ') {
        resultat += "%20";
    } else {
        resultat += caractere;
    }
}

return resultat;

}

</div>