Introduction aux chaînes de caractères

Les chaînes de caractères, souvent appelées strings, se distinguent des listes linéaires par leur focalisation sur des ensembles de caractères. Contrairement aux listes qui traitent des éléments individuels, les chaînes permettent principalement des opérations sur des sous-chaînes, c'est-à-dire des segments de caractères au sein d'une chaîne principale.

À noter qu'un tableau de caractères (comme char tableau[] = "salut") n'est pas équivalent à une chaîne de caractères (comme string chaine("salut")). L'utilisation de sizeof sur ces objets révèle des différences, car une chaîne encapsule un tableau avec des fonctions d'opérations supplémentaires.

Comparaison des chaînes

L'égalité entre chaînes requiert une longueur identique et une séquence de caractères identique. Pour l'ordre, la comparaison se base sur la position lexicographique des caractères et la longueur. Par exemple, "abc" est inférieur à "aeb" car 'b' précède 'e' dans l'ordre ASCII, tandis que "aaa" est supérieur à "aa" en raison de sa longueur.

Structures de stockage

Stockage séquentiel

Les chaînes sont stockées dans des tableaux à longueur fixe, où la longueur effective est souvent enregistrée dans le premier élément, par exemple longueur = tableau[0].

Stockage chaîné

Similaire à une liste chaînée, mais chaque nœud peut contenir un ou plusieurs caractères pour optimiser l'espace, évitant ainsi une surcharge due à un nœud par caractère.

Utilisation en C++

En C++, la bibliothèque <string> fournit la classe string, qui offre de nombreuses fonctionnalités intégrées.

Constructeurs de chaînes

Exemple de code illustrant les constructeurs :

#include <iostream>
#include <string>
using namespace std;

void demonstration_construction() {
    string vide;                 // Chaîne vide
    string copie(vide);          // Copie (ou string copie = vide;)
    string param("bonjour");     // Constructeur avec chaîne C
    string repetee(4, 'z');      // Chaîne avec 4 'z'
    string sous_chaine(param, 2, 3); // Extrait 3 caractères à partir de l'indice 2

    cout << "vide : " << vide << endl;
    cout << "copie : " << copie << endl;
    cout << "param : " << param << endl;
    cout << "repetee : " << repetee << endl;
    cout << "sous_chaine : " << sous_chaine << endl;
}

Membres courants de la classe string

Pour une chaîne str = "salut" et une sous-chaîne recherche = "al" :

Notes techniques :

• La position dans substr et find suit la logique des indices (commençant à 0).
• Utiliser sizeof(str) sur un objet string retourne la taille de la classe, pas la longueur de la chaîne.
• Combiner find et substr permet d'extraire des segments spécifiques, comme dans cet exemple :

void extraction_avancee() {
    string texte("Bonjour le monde, je suis Alice. Je viens de France.");
    
    // Recherche d'une séquence entre deux marqueurs
    size_t debut = texte.find("Alice");
    size_t fin = texte.find(".");
    
    if (debut != string::npos && fin != string::npos) {
        string segment = texte.substr(debut, fin - debut + 1);
        cout << "Segment extrait : " << segment << endl;
    }
}

Pour définir la longueur d'un tableau à la compilation, utiliser vector si la taille dépend de size() :

int longueur = str.size();
vector<char> tableau(longueur); // Alternative dynamique

Surcharge d'opérateurs

Algorithmes de recherche de motif

Dans la correspondance de motifs, la chaîne principale est la cible, et la sous-chaîne est le motif.

Algorithme naïf (BF - Brute Force)

L'algorithme BF parcourt la cible caractère par caractère pour trouver une correspondance exacte avec le motif.

Exemple d'implémentation en C++ :

#include <iostream>
#include <string>
using namespace std;

void recherche_BF() {
    string cible, motif;
    cout << "Entrez la cible et le motif : ";
    cin >> cible >> motif;

    int i = 0; // Indice pour la cible
    int correspondances = 0;

    while (i <= cible.size() - motif.size()) {
        int j = 0;
        int temp = i;
        int compteur = 0;

        // Vérification caractère par caractère
        while (temp < cible.size() && j < motif.size() && cible[temp] == motif[j]) {
            compteur++;
            temp++;
            j++;
        }

        if (compteur == motif.size()) {
            correspondances++;
            cout << "Motif trouvé à l'indice " << i << endl;
            break; // Arrêter à la première occurrence
        }
        i++;
    }

    if (correspondances == 0) {
        cout << "Motif non trouvé." << endl;
    }
}

Analyse de complexité :

• Cas défavorable : O((n-m+1)*m), où n est la longueur de la cible et m celle du motif.
• Cas favorable : O(n), si le motif est trouvé immédiatement.

Algorithme de Knuth-Morris-Pratt (KMP)

L'algorithme KMP optimise la recherche en évitant les comparaisons redondantes grâce à un prétraitement du motif, permettant de sauter des positions lors d'une incompatibilité.