Strängsökningsalgoritm (String Search) i C++- Förklaring, exempel och kod

Strängsökningsalgoritmen används för att hitta förekomster av ett specifikt mönster(delsträng) i en större text(sträng). Denna algoritm spelar en avgörande roll i textbearbetnings-, söknings- och manipuleringsuppgifter.

Hur det fungerar

1. Börja med en text(sträng) och ett mönster(delsträng) att söka efter.
2. Iterera genom texten ett tecken i taget.
3. För varje tecken i texten, jämför det med det första tecknet i mönstret.
4. Om det finns en matchning, kontrollera om de efterföljande tecknen också matchar mönstret.
5. Om mönstret är helt matchat, registrera startpositionen för matchen.
6. Fortsätt att söka efter mönstret i texten.

Exempel

Tänk på en text: "ababcababcabcabc" och ett mönster: "abc"

1. Börja vid position 0. Jämför "a" med det första tecknet "a" i mönstret.
2. Matchning hittades, flytta till nästa tecken: "b" med "b" och "a" med "c".
3. Fortsätt matcha: "b" med "a", "a" med "b" och "b" med "c".
4. Matchen misslyckades på plats 2.
5. Börja igen vid position 3. Jämför "a" med det första tecknet "a" i mönstret.
6. Lyckad matchning: "a" med "a", "b" med "b" och "c" med "c".
7. Rekordposition 3.

Mönstret "abc" finns på positionerna 0, 6 och 9.

Exempelkod i C++

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> stringSearch(const std::string& text, const std::string& pattern) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- pattern.length(); ++i) {  
        int j = 0;  
        while(j < pattern.length() && text[i + j] == pattern[j]) {  
            ++j;  
        }  
        if(j == pattern.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "ababcababcabcabc";  
    std::string pattern = "abc";  
  
    std::vector<int> result = stringSearch(text, pattern);  
  
    std::cout << "Pattern found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

I detta exempel stringSearch används funktionen för att hitta förekomster av mönstret "abc" i texten "ababcababcabcabc". Resultatet blir en vektor som innehåller startpositionerna för matcherna.