String Search Algorithm สำหรับข้อความสั้นใน C++ (Naive Search)

Naive String Search (Brute Force) เหมาะสำหรับข้อความสั้นและ pattern สั้น ทำงานโดยเปรียบเทียบตัวอักษรทีละตัว

อัลกอริทึม

1. เลื่อน pattern ไปทีละตัวบน text
2. ที่แต่ละตำแหน่ง เปรียบเทียบตัวอักษรทีละตัว
3. ถ้าตรงทุกตัว → พบ match
4. ถ้าไม่ตรง → ข้ามไปตำแหน่งถัดไป

Time Complexity: O(n×m) โดย n = text length, m = pattern length

ตัวอย่างโค้ด

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> naiveSearch(const string& text, const string& pattern) {
    vector<int> positions;
    int n = text.length();
    int m = pattern.length();
    
    if (m == 0 || n < m) return positions;
    
    for (int i = 0; i <= n - m; ++i) {
        bool match = true;
        for (int j = 0; j < m; ++j) {
            if (text[i + j] != pattern[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            positions.push_back(i);
        }
    }
    return positions;
}

int main() {
    string text, pattern;
    
    cout << "Enter text (no spaces): ";
    cin >> text;
    cout << "Enter pattern to search: ";
    cin >> pattern;
    
    auto positions = naiveSearch(text, pattern);
    
    if (positions.empty()) {
        cout << "No match found!\n";
    } else {
        cout << "Pattern found at positions: ";
        for (int pos : positions) {
            cout << pos << " ";
        }
        cout << "\nTotal instances: " << positions.size() << endl;
    }
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Enter text (no spaces): ababababa
Enter pattern to search: aba
Pattern found at positions: 0 2 4 6
Total instances: 4

การปรับปรุง: ใช้ string::find (Built-in)

#include <iostream>
#include <string>

using namespace std;

void findAll(const string& text, const string& pattern) {
    size_t pos = 0;
    int count = 0;
    
    while ((pos = text.find(pattern, pos)) != string::npos) {
        cout << "Found at position: " << pos << endl;
        ++count;
        ++pos;  // หา overlapping matches (ถ้าไม่ต้องการ overlapping ใช้ pos += pattern.length())
    }
    
    if (count == 0) cout << "No match found!\n";
    else cout << "Total: " << count << endl;
}

int main() {
    string text = "ababababa";
    string pattern = "aba";
    findAll(text, pattern);
    return 0;
}

Advanced: KMP Algorithm (Knuth-Morris-Pratt)

สำหรับข้อความยาว ควรใช้ KMP ซึ่งเป็น O(n+m)

vector<int> computeLPS(const string& pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);
    int len = 0, i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> positions;
    int n = text.length(), m = pattern.length();
    if (m == 0) return positions;
    
    vector<int> lps = computeLPS(pattern);
    int i = 0, j = 0;
    
    while (i < n) {
        if (text[i] == pattern[j]) {
            ++i; ++j;
        }
        if (j == m) {
            positions.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) j = lps[j - 1];
            else ++i;
        }
    }
    return positions;
}

เปรียบเทียบอัลกอริทึม String Search

สรุป

• ข้อความสั้น (< 1000 chars): Naive/Brute force เพียงพอ
• ข้อความยาวหรือ pattern ซับซ้อน: ใช้ KMP หรือ std::string::find
• Multiple patterns: ใช้ Aho-Corasick หรือ Rabin-Karp
• C++17+: std::string::find และ std::search optimized ดีแล้ว