C++ Program: Repeated String Search (Naive Algorithm)

การค้นหา Pattern ใน Text เดียวกันหลายครั้ง (Repeated Search) หาก Text คงที่ แต่ Pattern เปลี่ยนบ่อย ควรสร้าง Index/Data Structure ไว้ล่วงหน้า เช่น Suffix Array, Suffix Tree, Suffix Automaton

Naive Algorithm (Baseline)

สำหรับ Single Search โดยไม่มี Preprocessing

Complexity

• Time: O(N × M) Worst Case (N = Text Length, M = Pattern Length)
• Space: O(1)

โค้ด C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector naiveSearch(const string& text, const string& pattern) {
    vector positions;
    int n = text.length(), 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: "; getline(cin, text);
    cout << "Enter pattern: "; getline(cin, pattern);
    
    auto matches = naiveSearch(text, pattern);
    
    if (matches.empty()) {
        cout << "No match found\n";
    } else {
        for (int pos : matches) {
            cout << "Pattern found at position: " << pos << "\n";
        }
        cout << "Total matches: " << matches.size() << "\n";
    }
    return 0;
}

Output Example

Enter text: thisistutorialspoint.thisisac++program
Enter pattern: is
Pattern found at position: 2
Pattern found at position: 4
Pattern found at position: 23
Pattern found at position: 25
Total matches: 4

Data Structures สำหรับ Repeated Search (Text คงที่)

1. Suffix Array + LCP Array

• Build: O(N log N) หรือ O(N) (SA-IS)
• Search: O(M log N) Binary Search
• Space: O(N)

2. Suffix Tree (Ukkonen's Algorithm)

• Build: O(N)
• Search: O(M)
• Space: O(N) แต่ Constant สูง

3. Suffix Automaton (SAM)

• Build: O(N)
• Search: O(M)
• Space: O(N) States (≤ 2N-1)
• Bonus: นับ Occurrences, Longest Common Substring, Distinct Substrings ได้ง่าย

4. FM-Index / Burrows-Wheeler Transform

• Compressed Index, ใช้ Memory น้อยมาก
• Search: O(M)
• ใช้ใน Bioinformatics (BWA, Bowtie)

Suffix Automaton Implementation (ขั้นสูง)

struct SAMState {
    int len, link;
    array next;
    int firstPos = -1;
    SAMState() : len(0), link(-1) { next.fill(-1); }
};

class SuffixAutomaton {
    vector st;
    int last;
    
public:
    SuffixAutomaton(const string& s) {
        st.reserve(2 * s.size());
        st.emplace_back(); // State 0
        last = 0;
        for (char ch : s) extend(ch - 'a');
    }
    
    void extend(int c) {
        int cur = st.size();
        st.emplace_back();
        st[cur].len = st[last].len + 1;
        st[cur].firstPos = st[cur].len - 1;
        
        int p = last;
        while (p != -1 && st[p].next[c] == -1) {
            st[p].next[c] = cur;
            p = st[p].link;
        }
        
        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = st.size();
                st.push_back(st[q]);
                st[clone].len = st[p].len + 1;
                st[clone].firstPos = st[q].firstPos;
                
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }
    
    // Check if pattern exists
    bool contains(const string& pattern) {
        int state = 0;
        for (char ch : pattern) {
            int c = ch - 'a';
            if (state >= st.size() || st[state].next[c] == -1) return false;
            state = st[state].next[c];
        }
        return true;
    }
    
    // Count occurrences (requires topological sort by len)
    int countOccurrences(const string& pattern) {
        int state = 0;
        for (char ch : pattern) {
            int c = ch - 'a';
            if (state >= st.size() || st[state].next[c] == -1) return 0;
            state = st[state].next[c];
        }
        // Need to compute occurrence counts via DP on suffix link tree
        return 1; // Simplified
    }
};

Recommendation

C++ Program: Finite State Automaton (FSA) Based String Search
C++ Program: N-Queens Problem Solution (Backtracking)

1. โปรแกรมหาจุดกึ่งกลางเส้นตรงใน C++

2. โปรแกรมหาจุดศูนย์กลาง (Centroid) ของสามเหลี่ยมใน C++

3. การค้นหาแบบทวิภาค (Binary Search) ใน C++

4. ตรวจสอบ Identical BSTs โดยไม่สร้าง Tree ใน C++

Scenario	Recommended Approach
Single Search, Small Text	Naive / KMP / Boyer-Moore
Single Search, Large Text	KMP / Boyer-Moore / Two-Way
Multiple Patterns, Single Text	Aho-Corasick
Repeated Search, Static Text	Suffix Automaton / Suffix Array
Bioinformatics (Genome)	FM-Index / BWA / Minimap2
Full-text Search Engine	Inverted Index (Lucene, Tantivy)