Algorithme de correspondance de chaînes et son implémentation en C++

En programmation C++, les problèmes de correspondance de chaînes sont très courants. En termes simples, le problème de correspondance de chaîne est le processus de recherche d'une chaîne de modèle spécifique dans une chaîne de texte. Dans les applications pratiques, les algorithmes de correspondance de chaînes sont principalement utilisés dans des domaines tels que la recherche de texte, la reconnaissance d'images et le traitement du langage naturel. Cet article se concentrera sur les algorithmes de correspondance de chaînes couramment utilisés et leur implémentation en C++.

1. Algorithme naïf de correspondance de chaînes

L'algorithme naïf de correspondance de chaînes est également appelé algorithme de correspondance de recherche par force brute. L'idée est d'essayer successivement de faire correspondre la chaîne de modèle P à chaque position de la chaîne de texte T jusqu'à ce qu'une position correspondante soit trouvée ou que P n'existe pas dans l'ensemble de T. La complexité temporelle de cet algorithme est élevée, O(n*m), où n et m sont respectivement les longueurs de la chaîne de texte T et de la chaîne de motif P.

Le code C++ est implémenté comme suit :

void naive_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    for(int i = 0; i <= n-m; i++) {
        int j;
        for(j = 0; j < m; j++) {
            if(T[i+j] != P[j]) break;
        }
        if(j == m) {
            cout << "Pattern occurs with shift " << i << endl;
        }
    }
}

2. Algorithme de correspondance de chaînes KMP

L'algorithme de correspondance de chaînes KMP est un algorithme de correspondance de chaînes classique. Son idée principale est de faire correspondre le préfixe et le suffixe les plus longs de la chaîne de modèle P Préfixe commun. et le suffixe sont utilisés pour la correspondance afin d'éviter la correspondance répétée de caractères déjà correspondants dans la chaîne de texte T. La complexité temporelle de cet algorithme est O(n), où n est la longueur de la chaîne de texte.

Le code C++ est implémenté comme suit :

void get_next(string P, vector<int>& next) {
    int m = P.length();
    next[0] = -1;
    int i = 0;
    int j = -1;
    while(i < m) {
        if(j == -1 || P[i] == P[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

void kmp_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    vector<int> next(m+1);
    get_next(P, next);
    int i = 0;
    int j = 0;
    while(i < n) {
        if(j == -1 || T[i] == P[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
        if(j == m) {
            cout << "Pattern occurs with shift " << i-m << endl;
            j = next[j];
        }
    }
}

3. Algorithme de correspondance de chaînes BM

L'algorithme BM est un algorithme de correspondance de chaînes basé sur de mauvais caractères et de bonnes règles de suffixe. Son idée principale est d'ignorer les caractères correspondants en faisant correspondre le dernier caractère de la chaîne de modèle P et en prétraitant les caractères sans correspondance dans la chaîne de texte T. La complexité temporelle de cet algorithme est O(n).

Le code C++ est implémenté comme suit :

const int MAXCHAR = 256;

void bm_match(string T, string P) {
    int n = T.length();
    int m = P.length();
    vector<int> badchar(MAXCHAR, -1);
    for(int i = 0; i < m; i++) {
        badchar[int(P[i])] = i;
    }
    vector<int> suffix(m+1);
    vector<bool> prefix(m+1);
    get_suffix_prefix(P, suffix, prefix);
    int i = 0;
    while(i <= n-m) {
        int j = m-1;
        while(j >= 0 && P[j] == T[i+j]) j--;
        if(j < 0) {
            cout << "Pattern occurs with shift " << i << endl;
            i += (i+m < n) ? m-badchar[int(T[i+m])] : 1;
        } else {
            i += max(suffix[j+1], j-badchar[int(T[i+j])]);
        }
    }
}

Cet article présente principalement les algorithmes de correspondance de chaînes couramment utilisés et leur implémentation en C++. Bien que l’algorithme naïf de correspondance de chaînes soit simple, sa complexité temporelle est élevée, tandis que les algorithmes KMP et BM peuvent trouver la position correspondante plus rapidement. Parmi eux, l'algorithme KMP convient aux chaînes de motifs courtes et l'algorithme BM convient aux chaînes de motifs longues. Dans les applications réelles, nous devons choisir l'algorithme approprié pour la correspondance de chaînes en fonction de différentes situations.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!