Algoritmus textového vyhledávání (Text Search) v C++- vysvětlení, příklad a kód

Algoritmus Text Search je základní metodou při zpracování textu a vyhledávání informací. Tento algoritmus nám umožňuje lokalizovat a identifikovat výskyty podřetězce(nebo vzoru) v rámci většího kusu textu.

Jak to funguje

1. Začněte s větším textem(nebo dokumentem) a podřetězcem, který chcete vyhledat.
2. Postupně procházejte každý znak textu.
3. Porovnejte podřetězec s částí textu, která má stejnou délku jako podřetězec. Pokud je nalezena shoda, zaznamenejte aktuální pozici.
4. Přejděte na další pozici a pokračujte ve srovnání.

Příklad

Zvažte text: "Pojďme hledat podřetězec v tomto textu, abychom viděli, jak algoritmus funguje."

A podřetězec, který se má hledat: "podřetězec"

1. Začněte na pozici 0. Porovnejte Let' s "podřetězcem". Žádná shoda.
2. Přesuňte se na pozici 1. Porovnejte et's s "podřetězcem". Žádná shoda.
3. Přesuňte se na pozici 2. Porovnejte t's " s "podřetězcem". Žádná shoda.
4. Přesuňte se na pozici 3. Porovnejte 's s s "podřetězcem". Žádná shoda.
5. Přesuňte se na pozici 4. Porovnejte se s "podřetězcem". Žádná shoda.
6. Přesuňte se na pozici 5. Porovnejte sea s "podřetězcem". Žádná shoda.
7. Přesuňte se na pozici 6. Porovnejte earc s "podřetězcem". Žádná shoda.
8. Přesuňte se na pozici 7. Porovnejte arch s "podřetězcem". Žádná shoda.
9. Přesuňte se na pozici 8. Porovnejte rch " s "podřetězcem". Žádná shoda.
10. Přesuňte se na pozici 9. Porovnejte ch w s "podřetězcem". Žádná shoda.
11. Přesuňte se na pozici 10. Porovnejte h wi s "podřetězcem". Žádná shoda.
12. Přesuňte se na pozici 11. Porovnejte " wit s "podřetězcem". Žádná shoda.
13. Přesuňte se na pozici 12. Porovnejte with s "podřetězcem". Žádná shoda.
14. Přesuňte se na pozici 13. Porovnejte ithi s "podřetězcem". Žádná shoda.
15. Přesuňte se na pozici 14. Porovnejte thin s "podřetězcem". Žádná shoda.
16. Přesuňte se na pozici 15. Porovnejte hinn s "podřetězcem". Žádná shoda.
17. Přesuňte se na pozici 16. Porovnejte in t s "podřetězcem". Žádná shoda.
18. Přesuňte se na pozici 17. Porovnejte n th s "podřetězcem". Žádná shoda.
19. Přesuňte se na pozici 18. Porovnejte " thi s "podřetězcem". Žádná shoda.
20. Přesuňte se na pozici 19. Porovnejte this s "podřetězcem". Žádná shoda.
21. Přesuňte se na pozici 20. Porovnejte his " s "podřetězcem". Žádná shoda.
22. Přesuňte se na pozici 21. Porovnejte is t s "podřetězcem". Žádná shoda.
23. Přesuňte se na pozici 22. Porovnejte s te  s "podřetězcem". Žádná shoda.
24. Přesuňte se na pozici 23. Porovnejte ubst  s "podřetězcem". Žádná shoda.
25. Přesuňte se na pozici 24. Porovnejte bstr s "podřetězcem". Žádná shoda.
26. Přesuňte se na pozici 25. Porovnejte stre s "podřetězcem". Žádná shoda.
27. Přejděte na pozici 26. Porovnejte trin  s "podřetězcem". Žádná shoda.
28. Přesuňte se na pozici 27. Porovnejte ring  s "podřetězcem". Shoda nalezena, rekordní pozice 27.

Podřetězec "podřetězec" se nachází na pozici 27 v textu.

Příklad kódu v 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;  
}  

V tomto příkladu textSearch se funkce používá k nalezení pozic podřetězce "podřetězec" v textu. Výsledkem bude vektor obsahující počáteční pozice zápasů.