close

(Text Search) C++ Metin Arama Algoritması- Açıklama, Örnek ve Kod

Metin Arama algoritması, metin işleme ve bilgi almada temel bir yöntemdir. Bu algoritma, daha büyük bir metin parçası içinde bir alt dizenin(veya kalıbın) oluşumlarını bulmamıza ve tanımlamamıza olanak tanır.

Nasıl çalışır

  1. Daha büyük bir metin(veya belge) parçası ve aranacak bir alt dize ile başlayın.
  2. Metnin her karakterini sırayla yineleyin.
  3. Alt dizeyi, metnin alt dizeyle aynı uzunluğa sahip bir kısmıyla karşılaştırın. Bir eşleşme bulunursa, geçerli konumu kaydedin.
  4. Bir sonraki konuma geçin ve karşılaştırmaya devam edin.

Örnek

Metni düşünün: "Algoritmanın nasıl çalıştığını görmek için bu metin içinde bir alt dize arayalım."

Ve aranacak alt dize: "alt dize"

  1. 0 konumundan başlayın. Let' "Alt dize" ile karşılaştırın. Eşleşme yok.
  2. 1 konumuna gidin. et's "Alt dize" ile karşılaştırın. Eşleşme yok.
  3. 2. konuma geçin. t's " ile "alt dizi"yi karşılaştırın. Eşleşme yok.
  4. 3. konuma geçin. 's s "Alt dize" ile karşılaştırın. Eşleşme yok.
  5. 4. konuma geçin. se "Alt dize" ile karşılaştırın. Eşleşme yok.
  6. 5. konuma geçin. sea "Alt dize" ile karşılaştırın. Eşleşme yok.
  7. 6. konuma geçin. earc "Alt dize" ile karşılaştırın. Eşleşme yok.
  8. 7 konumuna gidin. arch "Alt dize" ile karşılaştırın. Eşleşme yok.
  9. 8. konuma geçin. rch " ile "alt dizi"yi karşılaştırın. Eşleşme yok.
  10. 9. konuma geçin. ch w "Alt dize" ile karşılaştırın. Eşleşme yok.
  11. 10. konuma geçin. h wi "Alt dize" ile karşılaştırın. Eşleşme yok.
  12. 11. konuma geçin. " wit ile "alt dizi"yi karşılaştırın. Eşleşme yok.
  13. 12. konuma geçin. with "Alt dize" ile karşılaştırın. Eşleşme yok.
  14. 13. konuma geçin. ithi "Alt dize" ile karşılaştırın. Eşleşme yok.
  15. 14. konuma geçin. thin "Alt dize" ile karşılaştırın. Eşleşme yok.
  16. 15. konuma geçin. hinn "Alt dize" ile karşılaştırın. Eşleşme yok.
  17. 16. konuma geçin. in t "Alt dize" ile karşılaştırın. Eşleşme yok.
  18. 17. konuma geçin. n th "Alt dize" ile karşılaştırın. Eşleşme yok.
  19. 18. konuma geçin. " thi ile "alt dizi"yi karşılaştırın. Eşleşme yok.
  20. 19 konumuna gidin. this "Alt dize" ile karşılaştırın. Eşleşme yok.
  21. 20 konumuna gidin. his " ile "alt dizi"yi karşılaştırın. Eşleşme yok.
  22. 21 konumuna gidin. is t "Alt dize" ile karşılaştırın. Eşleşme yok.
  23. 22. konuma geçin. s te  "Alt dize" ile karşılaştırın. Eşleşme yok.
  24. 23 konumuna gidin. ubst  "Alt dize" ile karşılaştırın. Eşleşme yok.
  25. 24. konuma geçin. bstr "Alt dize" ile karşılaştırın. Eşleşme yok.
  26. 25. konuma geçin. stre "Alt dize" ile karşılaştırın. Eşleşme yok.
  27. 26. konuma geçin. trin  "Alt dize" ile karşılaştırın. Eşleşme yok.
  28. 27. konuma geçin. ring  "Alt dize" ile karşılaştırın. Eşleşme bulundu, kayıt konumu 27.

"alt dize" alt dizesi, metin içinde 27. konumda bulunur.

C++'da Örnek Kod 

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

Bu örnekte textSearch işlev, "alt dize" alt dizesinin metin içindeki konumlarını bulmak için kullanılır. Sonuç, maçların başlangıç ​​konumlarını içeren bir vektör olacaktır.