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

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

2. 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];
        }
    }
}

3. 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!