Algorytm wyszukiwania tekstu (Text Search) w C++- wyjaśnienie, przykład i kod

Algorytm wyszukiwania tekstowego jest podstawową metodą przetwarzania tekstu i wyszukiwania informacji. Algorytm ten pozwala nam zlokalizować i zidentyfikować wystąpienia podłańcucha(lub wzorca) w większym fragmencie tekstu.

Jak to działa

1. Zacznij od większego fragmentu tekstu(lub dokumentu) i podłańcucha do wyszukania.
2. Przejrzyj kolejno każdy znak tekstu.
3. Porównaj podłańcuch z fragmentem tekstu, który ma taką samą długość jak podłańcuch. Jeśli zostanie znalezione dopasowanie, zapisz bieżącą pozycję.
4. Przejdź do następnej pozycji i kontynuuj porównanie.

Przykład

Rozważ tekst: „Wyszukajmy podłańcuch w tym tekście, aby zobaczyć, jak działa algorytm”.

I podłańcuch do wyszukania: „podłańcuch”

1. Zacznij od pozycji 0. Porównaj Let' z „podłańcuchem”. Nie pasuje.
2. Przejdź do pozycji 1. Porównaj et's z „podłańcuchem”. Nie pasuje.
3. Przejdź do pozycji 2. Porównaj t's " z "podłańcuchem". Brak dopasowania.
4. Przejdź do pozycji 3. Porównaj 's s z „podłańcuchem”. Nie pasuje.
5. Przejdź do pozycji 4. Porównaj se z „podłańcuchem”. Nie pasuje.
6. Przejdź do pozycji 5. Porównaj sea z „podłańcuchem”. Nie pasuje.
7. Przejdź do pozycji 6. Porównaj earc z „podłańcuchem”. Nie pasuje.
8. Przejdź do pozycji 7. Porównaj arch z „podłańcuchem”. Nie pasuje.
9. Przejdź do pozycji 8. Porównaj rch " z "podłańcuchem". Brak dopasowania.
10. Przejdź do pozycji 9. Porównaj ch w z „podłańcuchem”. Nie pasuje.
11. Przejdź do pozycji 10. Porównaj h wi z „podłańcuchem”. Nie pasuje.
12. Przejdź do pozycji 11. Porównaj " wit z "podłańcuchem". Brak dopasowania.
13. Przejdź do pozycji 12. Porównaj with z „podłańcuchem”. Nie pasuje.
14. Przejdź do pozycji 13. Porównaj ithi z „podłańcuchem”. Nie pasuje.
15. Przejdź do pozycji 14. Porównaj thin z „podłańcuchem”. Nie pasuje.
16. Przejdź do pozycji 15. Porównaj hinn z „podłańcuchem”. Nie pasuje.
17. Przejdź do pozycji 16. Porównaj in t z „podłańcuchem”. Nie pasuje.
18. Przejdź do pozycji 17. Porównaj n th z „podłańcuchem”. Nie pasuje.
19. Przejdź do pozycji 18. Porównaj " thi z "podłańcuchem". Brak dopasowania.
20. Przejdź do pozycji 19. Porównaj this z „podłańcuchem”. Nie pasuje.
21. Przejdź do pozycji 20. Porównaj his " z "podłańcuchem". Brak dopasowania.
22. Przejdź do pozycji 21. Porównaj is t z „podłańcuchem”. Nie pasuje.
23. Przejdź do pozycji 22. Porównaj s te  z „podłańcuchem”. Nie pasuje.
24. Przejdź do pozycji 23. Porównaj ubst  z „podłańcuchem”. Nie pasuje.
25. Przejdź do pozycji 24. Porównaj bstr z „podłańcuchem”. Nie pasuje.
26. Przejdź do pozycji 25. Porównaj stre z „podłańcuchem”. Nie pasuje.
27. Przejdź do pozycji 26. Porównaj trin  z „podłańcuchem”. Nie pasuje.
28. Przejdź do pozycji 27. Porównaj ring  z „podłańcuchem”. Znaleziono dopasowanie, pozycja rekordu 27.

Podłańcuch „substring” znajduje się na pozycji 27 w tekście.

Przykładowy kod w C++

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> textSearch(const std::string& text, const std::string& query) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- query.length(); ++i) {  
        int j = 0;  
        while(j < query.length() && text[i + j] == query[j]) {  
            ++j;  
        }  
        if(j == query.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "Let's search for a substring within this text to see how the algorithm works.";  
    std::string query = "substring";  
  
    std::vector<int> result = textSearch(text, query);  
  
    std::cout << "Substring found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

W tym przykładzie textSearch funkcja służy do znajdowania pozycji podłańcucha „substring” w tekście. Wynikiem będzie wektor zawierający początkowe pozycje meczów.