C++'da Dizi Arama (String Search) Algoritması- Açıklama, Örnek ve Kod

Dize arama algoritması, daha büyük bir metinde(dize) belirli bir modelin(alt dize) oluşumlarını bulmak için kullanılır. Bu algoritma, metin işleme, arama ve değiştirme görevlerinde çok önemli bir rol oynar.

Nasıl çalışır

1. Aranacak bir metin(dize) ve bir kalıp(alt dize) ile başlayın.
2. Metin boyunca her seferinde bir karakter yineleyin.
3. Metindeki her karakter için, kalıbın ilk karakteriyle karşılaştırın.
4. Bir eşleşme varsa, sonraki karakterlerin de kalıpla eşleşip eşleşmediğini kontrol edin.
5. Model tamamen eşleşirse, eşleşmenin başlangıç ​​konumunu kaydedin.
6. Metinde kalıbı aramaya devam edin.

Örnek

Bir metin düşünün: "ababcababcabcabc" Ve bir kalıp: "abc"

1. 0 konumundan başlayın. "a"yı modeldeki ilk "a" karakteriyle karşılaştırın.
2. Eşleşme bulundu, sonraki karakterlere geçin: "b" ile "b" ve "a" ile "c".
3. Eşleştirmeye devam edin: "b" ile "a", "a" ile "b" ve "b" ile "c".
4. Maç 2. pozisyonda başarısız oldu.
5. 3. konumdan yeniden başlayın. "a"yı modeldeki ilk "a" karakteriyle karşılaştırın.
6. Başarılı eşleştirme: "a" ile "a", "b" ile "b" ve "c" ile "c".
7. Kayıt konumu 3.

"abc" modeli 0, 6 ve 9 konumlarında bulunur.

C++'da Örnek Kod

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

Bu örnekte stringSearch işlev, "abc" kalıbının "ababcababcabcabc" metni içinde geçtiği yerleri bulmak için kullanılır. Sonuç, maçların başlangıç ​​konumlarını içeren bir vektör olacaktır.