อัลกอริทึม การค้นหาข้อความ (Text Search) ใน C++- คำอธิบาย ตัวอย่าง และโค้ด

อัลกอริทึมการค้นหาข้อความเป็นวิธีการพื้นฐานในการประมวลผลข้อความและการดึงข้อมูล อัลกอริทึมนี้ช่วยให้เราสามารถค้นหาและระบุการเกิดขึ้นของสตริงย่อย(หรือรูปแบบ) ภายในข้อความขนาดใหญ่

มันทำงานอย่างไร

1. เริ่มต้นด้วยข้อความ(หรือเอกสาร) ที่ใหญ่ขึ้นและสตริงย่อยเพื่อค้นหา
2. วนซ้ำผ่านอักขระแต่ละตัวของข้อความตามลำดับ
3. เปรียบเทียบสตริงย่อยกับส่วนของข้อความที่มีความยาวเท่ากันกับสตริงย่อย หากพบการแข่งขัน ให้บันทึกตำแหน่งปัจจุบัน
4. ย้ายไปยังตำแหน่งถัดไปและทำการเปรียบเทียบต่อไป

ตัวอย่าง

พิจารณาข้อความ: "ลองค้นหาสตริงย่อยภายในข้อความนี้เพื่อดูว่าอัลกอริทึมทำงานอย่างไร"

และสตริงย่อยเพื่อค้นหา: "substring"

1. เริ่มที่ตำแหน่ง 0 เปรียบเทียบ Let' กับ "substring" ไม่มีการแข่งขัน
2. ย้ายไปที่ตำแหน่ง 1 เปรียบเทียบ et's กับ "substring" ไม่มีการแข่งขัน
3. ย้ายไปตำแหน่ง 2 เปรียบเทียบ t's " กับ "substring" ไม่ตรงกัน
4. ย้ายไปตำแหน่ง 3 เปรียบเทียบ 's s กับ "substring" ไม่มีการแข่งขัน
5. ย้ายไปตำแหน่งที่ 4 เปรียบเทียบ se กับ "substring" ไม่มีการแข่งขัน
6. ย้ายไปตำแหน่ง 5 เปรียบเทียบ sea กับ "substring" ไม่มีการแข่งขัน
7. ย้ายไปตำแหน่ง 6 เปรียบเทียบ earc กับ "substring" ไม่มีการแข่งขัน
8. ย้ายไปตำแหน่ง 7 เปรียบเทียบ arch กับ "substring" ไม่มีการแข่งขัน
9. ย้ายไปตำแหน่ง 8 เปรียบเทียบ rch " กับ "substring" ไม่ตรงกัน
10. เลื่อนไปที่ตำแหน่ง 9 เปรียบเทียบ ch w กับ "substring" ไม่มีการแข่งขัน
11. ย้ายไปตำแหน่ง 10 เปรียบเทียบ h wi กับ "substring" ไม่มีการแข่งขัน
12. ย้ายไปตำแหน่ง 11 เปรียบเทียบ " wit กับ "substring" ไม่ตรงกัน
13. ย้ายไปตำแหน่ง 12 เปรียบเทียบ with กับ "substring" ไม่มีการแข่งขัน
14. ย้ายไปตำแหน่ง 13 เปรียบเทียบ ithi กับ "substring" ไม่มีการแข่งขัน
15. ย้ายไปตำแหน่ง 14 เปรียบเทียบ thin กับ "substring" ไม่มีการแข่งขัน
16. ย้ายไปตำแหน่ง 15 เปรียบเทียบ hinn กับ "substring" ไม่มีการแข่งขัน
17. ย้ายไปตำแหน่ง 16 เปรียบเทียบ in t กับ "substring" ไม่มีการแข่งขัน
18. ย้ายไปตำแหน่ง 17 เปรียบเทียบ n th กับ "substring" ไม่มีการแข่งขัน
19. ย้ายไปที่ตำแหน่ง 18 เปรียบเทียบ " thi กับ "substring" ไม่ตรงกัน
20. ย้ายไปตำแหน่ง 19 เปรียบเทียบ this กับ "substring" ไม่มีการแข่งขัน
21. ย้ายไปที่ตำแหน่ง 20 เปรียบเทียบ his " กับ "substring" ไม่ตรงกัน
22. ย้ายไปที่ตำแหน่ง 21 เปรียบเทียบ is t กับ "substring" ไม่มีการแข่งขัน
23. ย้ายไปตำแหน่ง 22 เปรียบเทียบ s te  กับ "substring" ไม่มีการแข่งขัน
24. ย้ายไปที่ตำแหน่ง 23 เปรียบเทียบ ubst  กับ "substring" ไม่มีการแข่งขัน
25. ย้ายไปตำแหน่ง 24 เปรียบเทียบ bstr กับ "substring" ไม่มีการแข่งขัน
26. ย้ายไปที่ตำแหน่ง 25 เปรียบเทียบ stre กับ "substring" ไม่มีการแข่งขัน
27. ย้ายไปที่ตำแหน่ง 26 เปรียบเทียบ trin  กับ "substring" ไม่มีการแข่งขัน
28. ย้ายไปตำแหน่ง 27 เปรียบเทียบ ring  กับ "substring" พบการแข่งขัน บันทึกตำแหน่ง 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" ภายในข้อความ ผลลัพธ์จะเป็นเวกเตอร์ที่มีตำแหน่งเริ่มต้นของการแข่งขัน