Heim > Artikel > Backend-Entwicklung > 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++.
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; } } }
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]; } } }
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!