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

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

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

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

ตัวอย่าง

พิจารณาข้อความ: "ababcababcabc" และรูปแบบ: "abc"

1. เริ่มต้นที่ตำแหน่ง 0 เปรียบเทียบ "a" กับอักขระตัวแรก "a" ในรูปแบบ
2. พบการจับคู่ ย้ายไปยังอักขระถัดไป: "b" กับ "b" และ "a" กับ "c"
3. จับคู่ต่อไป: "b" กับ "a", "a" กับ "b" และ "b" กับ "c"
4. การแข่งขันล้มเหลวในตำแหน่ง 2
5. เริ่มต้นอีกครั้งที่ตำแหน่ง 3 เปรียบเทียบ "a" กับอักขระตัวแรก "a" ในรูปแบบ
6. การจับคู่ที่ประสบความสำเร็จ: "a" กับ "a", "b" กับ "b" และ "c" กับ "c"
7. ตำแหน่งบันทึก3.

พบรูปแบบ "abc" ที่ตำแหน่ง 0, 6 และ 9

ตัวอย่างโค้ดในภาษา C++

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

ในตัวอย่างนี้ stringSearch ฟังก์ชันนี้ใช้เพื่อค้นหาการเกิดขึ้นของรูปแบบ "abc" ภายในข้อความ "ababcababcabcc" ผลลัพธ์จะเป็นเวกเตอร์ที่มีตำแหน่งเริ่มต้นของการแข่งขัน