Thuât·toán Z-Function, Hash Table

Giới thiệu thuật toán Z-Function và Hash Table

Mục lục

Giới thiệu chung

Trong lập trình nói chung và đặc biệt là trong lập trình thi đấu, thuật toán Z-Function và cấu trúc dữ liệu Hash Table đóng vai trò cực kỳ quan trọng, góp phần giải quyết hiệu quả nhiều bài toán phức tạp với độ phức tạp thời gian tối ưu. Z-Function là một thuật toán mạnh mẽ trong xử lý chuỗi, đặc biệt hữu dụng trong các bài toán như tìm kiếm mẫu con (pattern matching), đếm số lần xuất hiện của một chuỗi con trong chuỗi lớn, hay kiểm tra các tính chất đối xứng. Với độ phức tạp tuyến tính O(n), Z-Function giúp thay thế cho các giải pháp ngây thơ có độ phức tạp cao hơn, từ đó tối ưu hiệu năng chương trình – điều vô cùng quan trọng trong môi trường lập trình thi đấu, nơi thời gian xử lý là yếu tố then chốt. Trong khi đó, Hash Table – với các biến thể như unordered_map trong C++ hoặc dict trong Python – là một trong những cấu trúc dữ liệu nền tảng nhất, cho phép truy cập, chèn, và xóa phần tử với độ phức tạp trung bình là O(1). Cấu trúc này hỗ trợ mạnh mẽ trong việc đếm tần suất, lưu trạng thái đã duyệt, thiết kế bộ nhớ đệm (memoization), và giải các bài toán về ánh xạ hay tìm kiếm hiệu quả. Trong lập trình thi đấu, khả năng áp dụng nhanh chóng Hash Table để lưu trữ dữ liệu tạm thời hay kiểm tra điều kiện trong các bài toán yêu cầu tối ưu hóa tốc độ là một kỹ năng sống còn. Khi kết hợp cả hai – Z-Function cho xử lý chuỗi nhanh và Hash Table cho quản lý dữ liệu hiệu quả – lập trình viên có thể giải quyết một loạt các bài toán ở cấp độ cao, từ các bài toán chuỗi cổ điển đến các bài toán tổ hợp nâng cao, qua đó nâng cao khả năng phân tích, tư duy thuật toán và tối ưu hoá giải pháp. Vì vậy, việc nắm vững và hiểu sâu hai công cụ này không chỉ giúp giải bài nhanh và chính xác hơn, mà còn là nền tảng để phát triển tư duy thuật toán chuyên nghiệp trong cả học thuật lẫn công việc thực tế.

Trong bài viết này, chúng ta sẽ cùng tìm hiểu hai cấu trúc và thuật toán rất hữu ích trong lĩnh vực xử lý chuỗi và cấu trúc dữ liệu:

Z-Function: Thuật toán xử lý chuỗi giúp nhận diện các chuỗi con trùng với tiền tố của chuỗi gốc.
Hash Table (Bảng băm): Cấu trúc dữ liệu ánh xạ key – value, cho phép truy xuất nhanh chóng.

Chúng ta sẽ đi chi tiết vào từng chủ đề với các phần dưới đây.

Thuật toán Z-Function

1.1 Khái niệm và ý tưởng

Với một chuỗi S có độ dài n, ta định nghĩa mảng z như sau:

z[0] có thể quy ước là 0 hoặc bằng độ dài chuỗi.
Với i > 0, z[i] là độ dài chuỗi con bắt đầu từ vị trí i trùng với tiền tố của S.

Thuật toán duy trì đoạn [l, r] sao cho chuỗi S[l…r] trùng với tiền tố, giúp tính giá trị z[i] nhanh chóng.

Ví dụ minh họa Z-Function

Giả sử ta có chuỗi S = "abaaba". Ta sẽ tính mảng Z theo các bước sau:

Z[0]: Theo quy ước, ta gán Z[0] = 0.
Z[1]: So sánh chuỗi con từ vị trí 1 (“baaba“) với tiền tố (“abaaba“). Vì ký tự đầu khác nhau (b ≠ a), nên Z[1] = 0.
Z[2]: So sánh chuỗi con từ vị trí 2 (“aaba“) với tiền tố. Kết quả: khớp 1 ký tự (“a”) → Z[2] = 1.
Z[3]: So sánh chuỗi con từ vị trí 3 (“aba“) với tiền tố. Toàn bộ chuỗi “aba” khớp với tiền tố “aba” → Z[3] = 3.
Z[4]: Chuỗi con từ vị trí 4 (“ba“) không khớp với tiền tố do b ≠ a → Z[4] = 0.
Z[5]: Chuỗi con từ vị trí 5 (“a“) khớp với ký tự đầu tiên của tiền tố → Z[5] = 1.

Kết quả mảng Z của chuỗi "abaaba" là: [0, 0, 1, 3, 0, 1].

1.2 Ví dụ – Cách tính mảng Z (Code C++)

Đoạn code dưới đây minh họa cách tính mảng Z cho một chuỗi ngắn:


// Hàm tính mảng Z của chuỗi s
vector<int> computeZFunction(const string &s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r)
            z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

// Hàm demo để in kết quả từng bước của Z-Function cho chuỗi "abaaba"
void demoZFunction() {
    string s = "abaaba";
    vector<int> z = computeZFunction(s);
    cout << "Chuỗi: " << s << "n";
    cout << "Mảng Z:n";
    for (int i = 0; i < z.size(); i++) {
        cout << "z[" << i << "] = " << z[i] << "n";
    }
}

1.3 Ứng dụng trong bài toán tìm kiếm mẫu (pattern matching)

Để tìm mẫu P trong văn bản T, ta tạo chuỗi:

S = P + '$' + T

Tính mảng Z của S, và nếu z[i] bằng độ dài mẫu, ta biết mẫu xuất hiện tại vị trí i - |P| - 1 trong văn bản.


vector<int> computeZFunction(const string &s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r)
            z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

void patternMatchingDemo(const string &pattern, const string &text) {
    string s = pattern + "$" + text; // Kết hợp mẫu và văn bản
    vector<int> z = computeZFunction(s);
    int patternLength = pattern.size();
    
    cout << "Tìm mẫu "" << pattern << "" trong văn bản "" << text << "":n";
    for (int i = patternLength + 1; i < s.size(); i++) {
        if (z[i] == patternLength) {
            cout << "Mẫu tìm thấy tại vị trí: " << i - patternLength - 1 << "n";
        }
    }
}

1.4 Độ phức tạp và Nhận xét

Độ phức tạp: Thuật toán có độ phức tạp trung bình O(n), do mỗi ký tự chỉ được xử lý một vài lần với cơ chế duy trì khoảng [l, r].
Nhận xét: Z-Function rất hiệu quả trong xử lý xâu, đặc biệt với các bài toán tìm kiếm mẫu và so sánh xâu. Việc tái sử dụng kết quả đã tính toán giúp giảm thiểu phép so sánh thừa.

Hash Table

2.1 Khái niệm và thành phần cơ bản của Hash Table

Hash Table là cấu trúc dữ liệu ánh xạ key → value. Các thành phần chính gồm:

Hàm băm: Biến đổi key thành số nguyên chỉ số trong mảng.
Bảng chứa: Mảng các bucket chứa các cặp key–value.
Xử lý va chạm: Sử dụng phương pháp chaining (liên kết riêng) hoặc open addressing (định vị mở).

2.2 Ví dụ minh họa cơ bản với Hash Table

Đoạn code dưới đây minh họa việc cài đặt Hash Table đơn giản bằng phương pháp chaining:


class MyHashTable {
private:
    static const int TABLE_SIZE = 10007;
    vector<list<pair<int, int>>> table; // Mỗi bucket chứa cặp (key, value)
    
    int hashFunction(int key) {
        return key % TABLE_SIZE;
    }
    
public:
    MyHashTable() {
        table.resize(TABLE_SIZE);
    }
    
    void insert(int key, int value) {
        int hash_val = hashFunction(key);
        for (auto &p : table[hash_val]) {
            if (p.first == key) {
                p.second = value;
                return;
            }
        }
        table[hash_val].push_back(make_pair(key, value));
    }
    
    bool search(int key, int &value) {
        int hash_val = hashFunction(key);
        for (auto &p : table[hash_val]) {
            if (p.first == key) {
                value = p.second;
                return true;
            }
        }
        return false;
    }
    
    void remove(int key) {
        int hash_val = hashFunction(key);
        for (auto it = table[hash_val].begin(); it != table[hash_val].end(); it++) {
            if (it->first == key) {
                table[hash_val].erase(it);
                return;
            }
        }
    }
};

void demoHashTable() {
    MyHashTable ht;
    ht.insert(10, 100);
    ht.insert(20, 200);
    ht.insert(10017, 300);  // 10017 mod 10007 = 10 (va chạm với key 10)
    
    int value;
    if (ht.search(10, value))
        cout << "Key 10 có giá trị: " << value << "n";
    else
        cout << "Key 10 không tồn tạin";
    
    ht.remove(10);
    if (ht.search(10, value))
        cout << "Sau xoá, key 10 có giá trị: " << value << "n";
    else
        cout << "Sau xoá, key 10 không tồn tạin";
}

2.3 Ứng dụng – Đếm số phần tử xuất hiện sử dụng Hash Table

Một ứng dụng phổ biến của Hash Table là đếm số lần xuất hiện của các phần tử. Ví dụ, đoạn code dưới đây xây dựng ứng dụng đếm số nguyên trong mảng:


class FrequencyHashTable {
private:
    static const int TABLE_SIZE = 10007;
    vector<list<pair<int, int>>> table;
    
    int hashFunction(int key) {
        return key % TABLE_SIZE;
    }
    
public:
    FrequencyHashTable() {
        table.resize(TABLE_SIZE);
    }
    
    void add(int key) {
        int hash_val = hashFunction(key);
        for (auto &p : table[hash_val]) {
            if (p.first == key) {
                p.second++;
                return;
            }
        }
        table[hash_val].push_back(make_pair(key, 1));
    }
    
    void printFrequencies() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            for (auto &p : table[i]) {
                cout << "Phần tử " << p.first << " xuất hiện " << p.second << " lầnn";
            }
        }
    }
};

int main() {
    FrequencyHashTable freqHT;
    vector<int> arr = {1, 5, 3, 5, 2, 3, 3, 1, 4, 5};
    
    for (int x : arr) {
        freqHT.add(x);
    }
    
    cout << "Tần số xuất hiện của các phần tử trong mảng:n";
    freqHT.printFrequencies();
    return 0;
}

2.4 Độ phức tạp và Nhận xét

Độ phức tạp: Trong hầu hết các trường hợp, các thao tác chèn, tìm kiếm và xoá trong Hash Table có độ phức tạp trung bình là O(1). Tuy nhiên, nếu có nhiều va chạm, độ phức tạp có thể tăng lên O(n).
Nhận xét: Hash Table là cấu trúc dữ liệu mạnh mẽ, cho phép truy xuất và cập nhật dữ liệu rất nhanh. Việc lựa chọn hàm băm và xử lý va chạm một cách hiệu quả đóng vai trò quan trọng để tối ưu hóa hiệu năng của hệ thống.

Kết luận

Z-Function: Thuật toán Z-Function có độ phức tạp O(n) và là công cụ mạnh mẽ để xử lý chuỗi, ứng dụng trong tìm kiếm mẫu và so sánh xâu. Việc tối ưu hóa bằng cách tái sử dụng thông tin trong khoảng [l, r] giúp giảm thiểu phép so sánh không cần thiết.

Hash Table: Hash Table giúp ánh xạ các cặp key – value một cách nhanh chóng (trung bình O(1)) và là công cụ không thể thiếu trong lập trình, từ quản lý dữ liệu cho đến giải quyết các bài toán về bộ nhớ đệm, cơ sở dữ liệu.

Hy vọng bài viết này giúp bạn hiểu rõ hơn về thuật toán Z-Function là gì và bảng băm trong C++. Hãy theo dõi blog hướng dẫn lập trình của chúng tôi để cập nhật thêm nhiều bài học bổ ích về lập trình!