ტექსტის ძიების (Text Search) ალგორითმი C++ -ში- ახსნა, მაგალითი და კოდი

ტექსტის ძიების ალგორითმი არის ფუნდამენტური მეთოდი ტექსტის დამუშავებისა და ინფორმაციის მოძიებაში. ეს ალგორითმი საშუალებას გვაძლევს განვსაზღვროთ და ამოვიცნოთ ქვესტრიქონის(ან ნიმუშის) შემთხვევები ტექსტის უფრო დიდ ნაწილში.

Როგორ მუშაობს

1. დაიწყეთ ტექსტის(ან დოკუმენტის) უფრო დიდი ნაწილით და საძიებელი ქვესტრიქით.
2. თანმიმდევრულად გაიმეორეთ ტექსტის თითოეული სიმბოლო.
3. შეადარეთ ქვესტრიქონი ტექსტის ნაწილთან, რომელსაც აქვს იგივე სიგრძე, როგორც ქვესტრიქონი. თუ მატჩი იპოვეს, ჩაწერეთ მიმდინარე პოზიცია.
4. გადადით შემდეგ პოზიციაზე და განაგრძეთ შედარება.

მაგალითი

განვიხილოთ ტექსტი: "მოდით მოძებნოთ ქვესტრიქონი ამ ტექსტში, რათა ვნახოთ როგორ მუშაობს ალგორითმი."

და ქვესტრიქონი მოსაძებნად: "substring"

1. დაიწყეთ 0 პოზიციიდან. შეადარეთ Let' "substring". არანაირი მატჩი.
2. გადავიდეთ პოზიციაზე 1. შეადარეთ et's "substring". არანაირი მატჩი.
3. გადადით მე-2 პოზიციაზე. შეადარე t's " ქვესტრინგთან". არ არის შესატყვისი.
4. გადადით მე-3 პოზიციაზე. შეადარეთ 's s „ქვესტრინგს“. არანაირი მატჩი.
5. გადავიდეთ მე-4 პოზიციაზე. შეადარეთ se „ქვესტრინგს“. არანაირი მატჩი.
6. გადავიდეთ მე-5 პოზიციაზე. შეადარეთ sea „ქვესტრინგს“. არანაირი მატჩი.
7. გადადით მე-6 პოზიციაზე. შეადარეთ earc „ქვესტრინგს“. არანაირი მატჩი.
8. გადადით მე-7 პოზიციაზე. შეადარეთ arch „ქვესტრინგს“. არანაირი მატჩი.
9. გადადით მე-8 პოზიციაზე. შეადარეთ rch " ქვესტრინგთან". არ არის შესატყვისი.
10. გადადით მე-9 პოზიციაზე. შეადარეთ ch w „ქვესტრინგს“. არანაირი მატჩი.
11. გადავიდეთ მე-10 პოზიციაზე. შეადარეთ h wi „ქვესტრინგს“. არანაირი მატჩი.
12. გადადით 11-ე პოზიციაზე. შეადარეთ " wit " ქვესტრინგთან". თანხვედრა არ არის.
13. გადავიდეთ პოზიციაზე 12. შეადარეთ with „ქვესტრინგს“. არანაირი მატჩი.
14. გადავიდეთ პოზიციაზე 13. შეადარეთ ithi „ქვესტრინგს“. არანაირი მატჩი.
15. გადავიდეთ პოზიციაზე 14. შეადარეთ thin „ქვესტრინგს“. არანაირი მატჩი.
16. გადავიდეთ პოზიციაზე 15. შეადარეთ hinn „ქვესტრინგს“. არანაირი მატჩი.
17. გადავიდეთ პოზიციაზე 16. შეადარეთ in t „ქვესტრინგს“. არანაირი მატჩი.
18. გადავიდეთ პოზიციაზე 17. შეადარეთ n th „ქვესტრინგს“. არანაირი მატჩი.
19. გადავიდეთ პოზიციაზე 18. შეადარეთ " thi " ქვესტრინგთან". არ არის შესატყვისი.
20. გადავიდეთ მე-19 პოზიციაზე. შეადარეთ this „ქვესტრინგს“. არანაირი მატჩი.
21. გადადით 20-ე პოზიციაზე. შეადარეთ his " ქვესტრინგთან". თანხვედრა არ არის.
22. გადავიდეთ პოზიციაზე 21. შეადარეთ is t „ქვესტრინგს“. არანაირი მატჩი.
23. გადადით 22 პოზიციაზე. შეადარეთ s te  „ქვესტრინგს“. არანაირი მატჩი.
24. გადავიდეთ პოზიციაზე 23. შეადარეთ ubst  „ქვესტრინგს“. არანაირი მატჩი.
25. გადავიდეთ პოზიციაზე 24. შეადარეთ bstr „ქვესტრინგს“. არანაირი მატჩი.
26. გადავიდეთ პოზიციაზე 25. შეადარეთ stre „ქვესტრინგს“. არანაირი მატჩი.
27. გადავიდეთ პოზიციაზე 26. შეადარეთ trin  „ქვესტრინგს“. არანაირი მატჩი.
28. გადავიდეთ პოზიციაზე 27. შეადარეთ ring  „ქვესტრინგს“. ნაპოვნია მატჩი, რეკორდი პოზიცია 27.

ქვესტრიქონი "substring" გვხვდება ტექსტში 27 პოზიციაზე.

კოდის მაგალითი 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;  
}  

ამ მაგალითში textSearch ფუნქცია გამოიყენება ტექსტში ქვესტრიქონის "substring" პოზიციების მოსაძებნად. შედეგი იქნება ვექტორი, რომელიც შეიცავს მატჩების სასტარტო პოზიციებს.