Hiểu bài toán

Bài toán yêu cầu đếm số lần xuất hiện của xâu B trong xâu A. Các lần xuất hiện có thể chồng lấp lên nhau (overlapping). Ví dụ: với A = 'zyzyzyz' và B = 'zyz', có 3 lần xuất hiện tại các vị trí 0, 2, và 4 (nếu tính từ 0).

Các cách tiếp cận

Cách KMP (Knuth-Morris-Pratt)

#include <bits/stdc++.h>
using namespace std;

vector<int> buildPrefix(const string& p) {
    int m = p.size();
    vector<int> lps(m);
    for (int i = 1, len = 0; i < m; ) {
        if (p[i] == p[len]) lps[i++] = ++len;
        else if (len) len = lps[len - 1];
        else lps[i++] = 0;
    }
    return lps;
}

int main() {
    string a, b;
    cin >> a >> b;
    vector<int> lps = buildPrefix(b);
    int count = 0;
    for (int i = 0, j = 0; i < (int)a.size(); ) {
        if (a[i] == b[j]) {
            i++; j++;
            if (j == (int)b.size()) {
                count++;
                j = lps[j - 1];
            }
        } else if (j) j = lps[j - 1];
        else i++;
    }
    cout << count;
}

• Time Complexity: O(|A| + |B|)
• Space Complexity: O(|B|)

Thuật toán KMP tìm kiếm xâu con bằng cách sử dụng bảng tiền tố (LPS - Longest Prefix Suffix). Bước đầu tiên là xây dựng mảng LPS cho xâu B, cho biết độ dài tiền tố dài nhất cũng là hậu tố của xâu con B[0...i]. Khi duyệt xâu A, nếu có sự không khớp ký tự, thay vì lùi lại từ đầu, ta dùng mảng LPS để nhảy trực tiếp đến vị trí có thể khớp tiếp theo. Điều này đảm bảo độ phức tạp tuyến tính. Khi tìm thấy một lần xuất hiện đầy đủ của B trong A (j == |B|), ta tăng biến đếm và cập nhật j dựa trên LPS để tiếp tục tìm kiếm các lần xuất hiện chồng lấp.

Cách Hash (Rabin-Karp)

#include <bits/stdc++.h>
using namespace std;

const int base = 41;
const long long MOD = 1000000007;
const int MAX = 1000005;

long long hashA[MAX], POW[MAX];

long long getHash(int i, int j) {
    return (hashA[j] - hashA[i - 1] * POW[j - i + 1] + MOD * MOD) % MOD;
}

int main() {
    string a, b;
    cin >> a >> b;
    int lena = a.size(), lenb = b.size();

    if (lenb > lena) {
        cout << 0;
        return 0;
    }

    a = '%' + a;

    POW[0] = 1;
    for (int i = 1; i <= lena; i++) {
        POW[i] = (POW[i - 1] * base) % MOD;
    }

    long long hashB = 0;
    for (char c : b) {
        hashB = (hashB * base + (c - 'a' + 1)) % MOD;
    }

    for (int i = 1; i <= lena; i++) {
        hashA[i] = (hashA[i - 1] * base + (a[i] - 'a' + 1)) % MOD;
    }

    int count = 0;
    for (int i = 1; i <= lena - lenb + 1; i++) {
        if (getHash(i, i + lenb - 1) == hashB) {
            count++;
        }
    }
    cout << count;
}

• Time Complexity: O(|A| + |B|)
• Space Complexity: O(|A|)

Phương pháp Hash (Rabin-Karp) sử dụng mã hóa số học của các xâu. Ta tính giá trị băm của xâu B và giá trị băm của tất cả các xâu con trong A có cùng độ dài với B. Nếu giá trị băm khớp, ta mới so sánh ký tự để tránh lỗi va chạm (nếu có). Tuy nhiên, trong lập trình thi đấu thường chỉ so sánh giá trị băm nếu MOD đủ lớn. Ta có thể tính giá trị băm cho mọi xâu con trong A bằng cách sử dụng mảng tiền tố (prefix hash) và công thức lấy hash(i, j) = hash[j] - hash[i-1]*P[j-i+1].

Cách Brute Force

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

int main() {
    string a, b;
    cin >> a >> b;
    int count = 0;
    if (b.length() > a.length()) {
        cout << 0;
        return 0;
    }
    for (size_t i = 0; i <= a.length() - b.length(); ++i) {
        bool match = true;
        for (size_t j = 0; j < b.length(); ++j) {
            if (a[i + j] != b[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            count++;
        }
    }
    cout << count;
}

• Time Complexity: O(|A| * |B|)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Với mỗi vị trí có thể bắt đầu trong xâu A, ta thử so sánh ký tự từng cái một với xâu B. Nếu tất cả các ký tự đều khớp, ta tăng biến đếm. Phương pháp này đơn giản để cài đặt nhưng rất chậm với các xâu dài (ví dụ độ dài 10^6), dẫn đến Time Limit Exceeded.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Các lần xuất hiện có thể chồng lấp, ví dụ tìm 'aa' trong 'aaa' cho kết quả 2.
• Thuật toán KMP loại bỏ việc so sánh lại các ký tự đã biết, đảm bảo độ phức tạp O(N + M).
• Hashing cho phép so sánh các xâu con trong thời gian O(1) sau khi đã tiền xử lý.

Lỗi thường gặp

• Quên xử lý trường hợp độ dài B lớn hơn A.
• Trong KMP, sau khi tìm thấy một kết quả khớp full (j == M), cần gán j = lps[j-1] để tiếp tục tìm kiếm các kết quả chồng lấp thay vì reset j về 0.
• Lỗi tràn số (overflow) khi tính hash nếu không dùng modulo hoặc kiểu dữ liệu đủ lớn.