Heim  >  Artikel  >  Backend-Entwicklung  >  String-Matching-Algorithmus und seine Implementierung in C++

String-Matching-Algorithmus und seine Implementierung in C++

王林
王林Original
2023-08-22 09:13:521532Durchsuche

Bei der C++-Programmierung treten String-Matching-Probleme sehr häufig auf. Einfach ausgedrückt besteht das Problem der Zeichenfolgenübereinstimmung darin, eine bestimmte Musterzeichenfolge in einer Textzeichenfolge zu finden. In praktischen Anwendungen werden String-Matching-Algorithmen hauptsächlich in Bereichen wie Textsuche, Bilderkennung und Verarbeitung natürlicher Sprache verwendet. Dieser Artikel konzentriert sich auf die häufig verwendeten String-Matching-Algorithmen und ihre Implementierung in C++.

  1. Naiver String-Matching-Algorithmus

Naiver String-Matching-Algorithmus wird auch Brute-Force-Search-Matching-Algorithmus genannt. Die Idee besteht darin, nacheinander zu versuchen, die Musterzeichenfolge P an jeder Position der Textzeichenfolge T abzugleichen, bis eine übereinstimmende Position gefunden wird oder P nicht im gesamten T existiert. Die zeitliche Komplexität dieses Algorithmus ist hoch, O(n*m), wobei n und m die Längen der Textzeichenfolge T bzw. der Musterzeichenfolge P sind.

Der C++-Code ist wie folgt implementiert:

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;
        }
    }
}
  1. KMP-String-Matching-Algorithmus

KMP-String-Matching-Algorithmus ist ein klassischer String-Matching-Algorithmus. Seine Kernidee besteht darin, das längste Präfix und Suffix des gemeinsamen Präfixes P der Musterzeichenfolge abzugleichen und Suffix werden zum Abgleich verwendet, um ein wiederholtes Abgleichen bereits übereinstimmender Zeichen in der Textzeichenfolge T zu vermeiden. Die zeitliche Komplexität dieses Algorithmus beträgt O(n), wobei n die Länge der Textzeichenfolge ist.

Der C++-Code ist wie folgt implementiert:

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];
        }
    }
}
  1. BM-String-Matching-Algorithmus

BM-Algorithmus ist ein String-Matching-Algorithmus, der auf Regeln für schlechte Zeichen und gute Suffixe basiert. Seine Kernidee besteht darin, die übereinstimmenden Zeichen zu überspringen, indem das letzte Zeichen der Musterzeichenfolge P abgeglichen und die nicht übereinstimmenden Zeichen in der Textzeichenfolge T vorverarbeitet werden. Die zeitliche Komplexität dieses Algorithmus beträgt O(n).

Der C++-Code ist wie folgt implementiert:

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])]);
        }
    }
}

Dieser Artikel stellt hauptsächlich die häufig verwendeten String-Matching-Algorithmen und ihre Implementierung in C++ vor. Obwohl der naive String-Matching-Algorithmus einfach ist, ist seine zeitliche Komplexität hoch, während die KMP- und BM-Algorithmen die Matching-Position schneller finden können. Unter diesen eignet sich der KMP-Algorithmus für kurze Musterzeichenfolgen und der BM-Algorithmus für lange Musterzeichenfolgen. In tatsächlichen Anwendungen müssen wir je nach Situation den geeigneten Algorithmus für den String-Abgleich auswählen.

Das obige ist der detaillierte Inhalt vonString-Matching-Algorithmus und seine Implementierung in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn