Trang chủ Bài tập Kỳ thi Bài nộp Xếp hạng Thảo luận Trợ giúp
Đăng nhập Đăng ký
Thảo luận
Khu vực thảo luận

CHUYÊN ĐỀ XỬ LÝ CHUỖI (STRING PROCESSING)

Trùm CUỐI 2025-06-24 10:16:16 2025-06-24 10:27:48

Mục tiêu:

  • Thành thạo các thao tác xử lý chuỗi cơ bản.
  • Nắm vững và cài đặt được các thuật toán khớp chuỗi kinh điển: Hash chuỗi và KMP.
  • Hiểu và vận dụng được các cấu trúc dữ liệu và thuật toán mạnh cho chuỗi: Trie, Z-function.
  • Nhận diện và áp dụng đúng công cụ cho từng dạng bài toán xử lý chuỗi.
  • Có cái nhìn tổng quan về các kỹ thuật nâng cao để định hướng học tập sâu hơn.

NỘI DUNG CHI TIẾT

Lời Mở Đầu

Xử lý chuỗi (String Processing) là một trong những lĩnh vực quan trọng và có mặt ở khắp mọi nơi trong khoa học máy tính. Từ những tác vụ đơn giản như tìm kiếm một từ trong văn bản, kiểm tra email hợp lệ, cho đến các ứng dụng phức tạp như phân tích dữ liệu gene trong sinh học tin học, xây dựng bộ máy tìm kiếm (search engine), hay xử lý ngôn ngữ tự nhiên, chuỗi ký tự luôn là một dạng dữ liệu cốt lõi.

Trong lập trình thi đấu, các bài toán về chuỗi xuất hiện với tần suất cao, trải dài từ các vòng loại cơ bản đến các kỳ thi quốc tế. Việc nắm vững các kỹ thuật xử lý chuỗi không chỉ giúp bạn giải quyết các bài toán đặc thù mà còn rèn luyện tư duy thuật toán sắc bén.

Chuyên đề này sẽ dẫn dắt bạn qua một lộ trình học tập có hệ thống:

  1. Làm chủ công cụ: Bắt đầu với việc sử dụng thành thạo thư viện std::string của C++, nền tảng cho mọi thao tác.
  2. Thuật toán kinh điển: Đi sâu vào hai "vũ khí" mạnh mẽ và phổ biến nhất là Hash chuỗi (Rabin-Karp) và KMP, hai cách tiếp cận khác nhau cho bài toán tìm kiếm mẫu.
  3. Cấu trúc dữ liệu chuyên dụng: Khám phá Trie và Z-function, những công cụ hiệu quả cho các bài toán liên quan đến tập hợp chuỗi, tiền tố và hậu tố.
  4. Mở rộng tầm nhìn: Giới thiệu tổng quan về các kỹ thuật siêu nâng cao như Mảng Hậu tố (Suffix Array) và Tự động Hậu tố (Suffix Automaton) để bạn có định hướng nghiên cứu sâu hơn.

Hãy cùng bắt đầu hành trình chinh phục các thuật toán xử lý chuỗi!

Phần I: Xử lý chuỗi cơ bản với C++

Mục tiêu: Đảm bảo học sinh không mất điểm ở các thao tác đơn giản và sử dụng thư viện chuẩn một cách hiệu quả.

1. Sử dụng std::string:

Thư viện <string> của C++ cung cấp lớp std::string vô cùng mạnh mẽ và tiện lợi.

  • Khai báo, nhập/xuất:

    • Khai báo: string s;, string s = "hello";
    • Nhập từ cin: cin >> s; - Lưu ý: cách này chỉ đọc được một từ, dừng lại khi gặp khoảng trắng hoặc ký tự xuống dòng.
    • Nhập cả dòng với getline: getline(cin, s); - Đọc toàn bộ dòng cho đến khi gặp ký tự xuống dòng. Đây là cách nhập chuỗi có khoảng trắng an toàn nhất. Để tránh lỗi trôi lệnh sau khi dùng cin, bạn có thể cần dùng cin.ignore(); trước getline.

  • Các thao tác cơ bản:

    • Nối chuỗi: Dùng toán tử + hoặc +=.
      string s1 = "hello";
string s2 = " world";
string s3 = s1 + s2; // s3 = "hello world"
s1 += s2; // s1 bây giờ là "hello world"
    • Truy cập ký tự: Dùng toán tử [] (tương tự mảng). Chỉ số bắt đầu từ 0.
      string s = "abc";
char c = s[1]; // c = 'b'
    • Lấy độ dài: Dùng .length() hoặc .size(). Cả hai đều trả về độ dài chuỗi và có độ phức tạp O(1) .
      string s = "vietnam";
int len = s.length(); // len = 7

  • Các hàm hữu ích:

    • substr(pos, len): Lấy chuỗi con từ vị trí pos với độ dài len. Độ phức tạp là O(len) .
      string s = "abcdef";
string sub = s.substr(1, 3); // sub = "bcd"
    • find(pattern): Tìm vị trí xuất hiện đầu tiên của chuỗi pattern. Trả về string::npos nếu không tìm thấy.
      string text = "this is a test";
string pattern = "is";
size_t pos = text.find(pattern); // pos = 2
if (text.find("xyz") == string::npos) {
    // không tìm thấy "xyz"
}
    • push_back(char) & pop_back(): Thêm/xóa ký tự ở cuối chuỗi. Thao tác này thường có độ phức tạp trung bình là O(1) .
      string s = "cat";
s.push_back('s'); // s = "cats"
s.pop_back();     // s = "cat"

  • Lưu ý hiệu năng: Việc nối chuỗi bằng toán tử + trong vòng lặp (s = s + T) có thể rất chậm vì mỗi lần nối, một chuỗi mới được tạo ra và chuỗi cũ bị hủy. Sử dụng toán tử += (s += T) sẽ hiệu quả hơn nhiều.

2. Code Mẫu:

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

int main() {
    // Khai báo và khởi tạo
    std::string s1 = "Hello";
    std::string s2;

    // Nhập chuỗi (có khoảng trắng)
    std::cout << "Nhap ten cua ban: ";
    std::getline(std::cin, s2);

    // Nối chuỗi
    std::string greeting = s1 + ", " + s2 + "!";
    std::cout << greeting << std::endl;

    // Độ dài và truy cập ký tự
    std::cout << "Ten cua ban co " << s2.length() << " ky tu." << std::endl;
    if (!s2.empty()) {
        std::cout << "Ky tu dau tien la: " << s2[0] << std::endl;
    }

    // Lấy chuỗi con
    std::string sub = greeting.substr(0, 5);
    std::cout << "Chuoi con 5 ky tu dau: " << sub << std::endl;

    // Tìm kiếm
    size_t pos = greeting.find(s2);
    if (pos != std::string::npos) {
        std::cout << "Ten cua ban bat dau tai vi tri: " << pos << std::endl;
    }

    return 0;
}

Phần II: Các Thuật Toán Khớp Chuỗi Kinh Điển

Mục tiêu: Nắm vững hai công cụ mạnh mẽ và phổ biến nhất để giải quyết bài toán tìm kiếm mẫu trong văn bản.

A. Hash Chuỗi (Rolling Hash) và Thuật toán Rabin-Karp

  1. Ý tưởng cốt lõi: Thay vì so sánh hai chuỗi ký tự một cách trực tiếp, ta biến đổi mỗi chuỗi thành một con số duy nhất (hoặc gần như duy nhất) gọi là giá trị hash. Việc so sánh hai số nguyên lớn nhanh hơn rất nhiều so với việc so sánh từng ký tự của hai chuỗi.

  2. Kỹ thuật Rolling Hash: Để áp dụng cho việc tìm kiếm, ta cần tính hash của mọi chuỗi con có cùng độ dài với mẫu. Kỹ thuật "lăn" (rolling) giúp thực hiện điều này một cách hiệu quả.

    • Công thức hash đa thức: Ta xem một chuỗi S như một số ở hệ cơ số p .

      hash(S)=(\sum_{i=0}^{|S|-1} s_i \cdot p^i) \pmod{m}

      Trong đó:

      • s_i là giá trị số của ký tự thứ i (ví dụ: a -> 1, b -> 2, ...).
      • p là một cơ số, thường chọn là một số nguyên tố lớn hơn kích thước bảng chữ cái (ví dụ, 31 hoặc 53 cho bảng chữ cái tiếng Anh thường).
      • m là một modulo lớn, thường là một số nguyên tố lớn (ví dụ, 10^9 + 7 hoặc 10^9 + 9 ) để giảm xác suất xung đột.

    • Kỹ thuật "lăn": Giả sử ta đã có hash của chuỗi con S[i..i+k-1] . Để tính hash của chuỗi con tiếp theo S[i+1..i+k] trong O(1) , ta chỉ cần:

      1. Trừ đi phần của ký tự đầu tiên: s_i \cdot p^0 .
      2. Chia toàn bộ cho p .
      3. Cộng thêm phần của ký tự mới: s_{i+k} \cdot p^{k-1} .

      Công thức đầy đủ:

      hash(S[i+1..i+k]) = ( (hash(S[i..i+k-1]) - s_i) \cdot p^{-1} + s_{i+k} \cdot p^{k-1} ) \pmod{m}

      (Lưu ý: p^{-1} là nghịch đảo modular của p theo modulo m ).

  3. Xử lý xung đột (Collision):

    • Hiện tượng: Xung đột xảy ra khi hai chuỗi khác nhau nhưng lại có cùng một giá trị hash. Điều này có thể xảy ra do phép toán modulo.
    • Giải pháp:
      • Kiểm tra lại: Khi tìm thấy hai giá trị hash bằng nhau, ta so sánh trực tiếp hai chuỗi gốc để đảm bảo chúng thực sự giống nhau.
      • Hash kép (Double Hashing): Sử dụng hai cặp cơ số và modulo khác nhau (p_1, m_1) và (p_2, m_2) . Hai chuỗi được coi là bằng nhau chỉ khi cả hai cặp giá trị hash của chúng đều bằng nhau. Kỹ thuật này giảm xác suất xung đột xuống cực kỳ thấp, đến mức có thể bỏ qua bước kiểm tra lại trong các cuộc thi lập trình.

  4. Ứng dụng:

    • Tìm kiếm mẫu P trong văn bản T (Rabin-Karp): Tính hash của P. Sau đó dùng rolling hash để tính hash của mọi chuỗi con độ dài |P| trong T và so sánh. Độ phức tạp trung bình là O(|T| + |P|) .
    • Tìm chuỗi con chung dài nhất: Kết hợp hash và tìm kiếm nhị phân theo độ dài chuỗi con.
    • Đếm số chuỗi con khác nhau: Tính hash của tất cả các chuỗi con và đếm số lượng hash khác nhau.
    • Tìm chuỗi đối xứng (palindrome) dài nhất.

  5. Code Template (Double Hashing):

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

using namespace std;

struct RollingHash {
    long long p1 = 31, m1 = 1e9 + 7;
    long long p2 = 53, m2 = 1e9 + 9;
    string s;
    int n;
    vector<long long> hash1, hash2;
    vector<long long> p_pow1, p_pow2;
    vector<long long> inv_p1, inv_p2;

    long long power(long long base, long long exp, long long mod) {
        long long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }

    long long modInverse(long long n, long long mod) {
        return power(n, mod - 2, mod);
    }

    RollingHash(const string& str) {
        s = str;
        n = s.length();
        p_pow1.resize(n + 1);
        p_pow2.resize(n + 1);
        inv_p1.resize(n + 1);
        inv_p2.resize(n + 1);
        hash1.resize(n + 1, 0);
        hash2.resize(n + 1, 0);

        p_pow1[0] = 1; p_pow2[0] = 1;
        inv_p1[0] = 1; inv_p2[0] = 1;
        long long p_inv1 = modInverse(p1, m1);
        long long p_inv2 = modInverse(p2, m2);

        for (int i = 1; i <= n; ++i) {
            p_pow1[i] = (p_pow1[i - 1] * p1) % m1;
            p_pow2[i] = (p_pow2[i - 1] * p2) % m2;
            inv_p1[i] = (inv_p1[i - 1] * p_inv1) % m1;
            inv_p2[i] = (inv_p2[i - 1] * p_inv2) % m2;
        }

        for (int i = 0; i < n; ++i) {
            hash1[i + 1] = (hash1[i] + (s[i] - 'a' + 1) * p_pow1[i]) % m1;
            hash2[i + 1] = (hash2[i] + (s[i] - 'a' + 1) * p_pow2[i]) % m2;
        }
    }

    // Lấy hash của chuỗi con từ vị trí i đến j (0-based)
    pair<long long, long long> get_hash(int i, int j) {
        long long h1 = (hash1[j + 1] - hash1[i] + m1) % m1;
        long long h2 = (hash2[j + 1] - hash2[i] + m2) % m2;
        h1 = (h1 * inv_p1[i]) % m1;
        h2 = (h2 * inv_p2[i]) % m2;
        return {h1, h2};
    }
};

B. Thuật toán KMP (Knuth-Morris-Pratt)

  1. Ý tưởng cốt lõi: KMP là một thuật toán tìm kiếm chuỗi không bao giờ quay lại (re-scan) các ký tự trong văn bản. Khi xảy ra một sự không khớp, thay vì dịch chuyển mẫu đi 1 vị trí và so sánh lại từ đầu, KMP sử dụng thông tin từ chính các tiền tố của mẫu đã khớp để thực hiện một bước "trượt" thông minh, bỏ qua các vị trí chắc chắn không khớp.

  2. Hàm tiền xử lý - Mảng LPS (Longest Proper Prefix which is also Suffix): Đây là trái tim của KMP. Mảng lps (hay còn gọi là hàm \\pi hoặc mảng failure) được xây dựng dựa trên chuỗi mẫu pattern.

    • Định nghĩa: lps[i] là độ dài của tiền tố riêng dài nhất của chuỗi con pattern[0...i] mà cũng đồng thời là hậu tố của chuỗi con đó. (Tiền tố riêng là tiền tố không phải toàn bộ chuỗi).
    • Ví dụ minh họa: Với mẫu P = ababaca:
      • P[0...0] = a: lps[0] = 0
      • P[0...1] = ab: lps[1] = 0
      • P[0...2] = aba: Tiền tố a cũng là hậu tố. lps[2] = 1.
      • P[0...3] = abab: Tiền tố ab cũng là hậu tố. lps[3] = 2.
      • P[0...4] = ababa: Tiền tố aba cũng là hậu tố. lps[4] = 3.
      • P[0...5] = ababac: lps[5] = 0
      • P[0...6] = ababaca: Tiền tố a cũng là hậu tố. lps[6] = 1. => Mảng lps là: [0, 0, 1, 2, 3, 0, 1]
    • Thuật toán xây dựng lps: Có thể xây dựng mảng này trong thời gian tuyến tính O(|pattern|) bằng phương pháp quy hoạch động.

  3. Thuật toán tìm kiếm: Ta dùng hai con trỏ: i cho văn bản text và j cho mẫu pattern.

    1. Khi text[i] == pattern[j], tăng cả i và j.
    2. Nếu j đạt đến độ dài của pattern, ta đã tìm thấy một vị trí khớp. Để tìm các vị trí khớp tiếp theo, ta "trượt" pattern đi bằng cách gán j = lps[j-1].
    3. Khi text[i] != pattern[j]:
      • Nếu j > 0, ta không cần quay lại i. Ta chỉ cần lùi j về lps[j-1]. Điều này tương đương với việc trượt mẫu đi sao cho tiền tố pattern[0...lps[j-1]-1] (đã biết là khớp với hậu tố của phần đã so sánh) thẳng hàng với văn bản.
      • Nếu j == 0, không có tiền tố nào để tận dụng, ta chỉ cần tăng i lên.
    • Độ phức tạp: Toàn bộ quá trình tìm kiếm và tiền xử lý có độ phức tạp là O(|text| + |pattern|) .

  4. Ưu và nhược điểm so với Hash:

    • Ưu điểm:
      • Chính xác 100%: Không có hiện tượng xung đột.
      • Độ phức tạp worst-case được đảm bảo: Luôn là O(|T|+|P|) , trong khi Rabin-Karp có thể lên tới O(|T| \\cdot |P|) trong trường hợp xấu nhất (nhiều xung đột).
    • Nhược điểm:
      • Cài đặt phức tạp hơn: Khó hiểu và cài đặt hơn so với Rolling Hash.
      • Kém linh hoạt: Hash chuỗi có thể dễ dàng mở rộng cho các bài toán so sánh hai chuỗi con bất kỳ, đếm chuỗi con khác nhau, v.v., trong khi KMP chủ yếu được thiết kế cho bài toán tìm kiếm mẫu.

  5. Code Template:

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

// Hàm xây dựng mảng LPS cho KMP
std::vector<int> computeLPS(const std::string& pattern) {
    int m = pattern.length();
    std::vector<int> lps(m, 0);
    int length = 0; // Độ dài của tiền tố dài nhất trước đó cũng là hậu tố
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// Thuật toán tìm kiếm KMP
void KMPSearch(const std::string& text, const std::string& pattern) {
    int n = text.length();
    int m = pattern.length();
    std::vector<int> lps = computeLPS(pattern);
    int i = 0; // con trỏ cho text
    int j = 0; // con trỏ cho pattern

    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }

        if (j == m) {
            std::cout << "Tim thay mau tai vi tri " << i - j << std::endl;
            j = lps[j - 1];
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
}

Phần III: Các Cấu Trúc và Thuật Toán Nâng Cao

Mục tiêu: Trang bị các công cụ mạnh mẽ để giải quyết các bài toán liên quan đến tập hợp chuỗi và tiền tố/hậu tố.

A. Cây Tiền Tố (Trie / Prefix Tree)

  1. Ý tưởng và cấu trúc:

    • Trie là một cấu trúc dữ liệu dạng cây được sử dụng để lưu trữ một tập hợp các chuỗi.
    • Mỗi cạnh của cây được gán một ký tự.
    • Mỗi đường đi từ gốc xuống một nút bất kỳ đại diện cho một tiền tố.
    • Các từ hoàn chỉnh được đánh dấu bằng một cờ đặc biệt tại nút cuối cùng của từ đó.
    • Cấu trúc một nút:
      • Một mảng (hoặc std::map) các con trỏ tới các nút con, mỗi con trỏ tương ứng với một ký tự trong bảng chữ cái.
      • Một biến boolean (hoặc số nguyên) isEndOfWord để đánh dấu đây có phải là ký tự cuối cùng của một từ trong tập hợp hay không.

  2. Các thao tác cơ bản:

    • insert(string): Để chèn một chuỗi, ta duyệt từ gốc. Với mỗi ký tự, nếu chưa có đường đi (cạnh) tương ứng, ta tạo một nút mới. Cuối cùng, đánh dấu isEndOfWord tại nút cuối cùng.
    • search(string): Duyệt cây theo các ký tự của chuỗi. Nếu duyệt hết chuỗi và nút cuối cùng có cờ isEndOfWord là true, từ đó tồn tại trong tập hợp.
    • startsWith(prefix): Tương tự search, nhưng chỉ cần duyệt hết chuỗi tiền tố. Nếu có thể duyệt hết, tức là có ít nhất một từ bắt đầu bằng tiền tố đó.

  3. Phân tích độ phức tạp: Tất cả các thao tác trên (insert, search, startsWith) đều có độ phức tạp là O(L) , với L là độ dài của chuỗi cần thao tác, độc lập với số lượng chuỗi đã có trong Trie.

  4. Ứng dụng:

    • Hệ thống tự động điền (Autocomplete): Khi người dùng gõ một tiền tố, ta có thể tìm nút tương ứng với tiền tố đó trong Trie và duyệt tất cả các cây con từ đó để gợi ý các từ hoàn chỉnh.
    • Kiểm tra chính tả.
    • Đếm số chuỗi có tiền tố chung.
    • Giải các bài toán XOR (Trie nhị phân): Biểu diễn các số nguyên dưới dạng chuỗi nhị phân và chèn vào Trie. Cấu trúc này giúp giải quyết các bài toán như tìm cặp có XOR lớn nhất/nhỏ nhất, tìm phần tử trong mảng có XOR lớn nhất với một số cho trước.

  5. Code Template (Sử dụng mảng con trỏ):

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

const int ALPHABET_SIZE = 26;

struct TrieNode {
    TrieNode* children[ALPHABET_SIZE];
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            children[i] = nullptr;
        }
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    void insert(const std::string& key) {
        TrieNode* pCrawl = root;
        for (char ch : key) {
            int index = ch - 'a';
            if (!pCrawl->children[index]) {
                pCrawl->children[index] = new TrieNode();
            }
            pCrawl = pCrawl->children[index];
        }
        pCrawl->isEndOfWord = true;
    }

    bool search(const std::string& key) {
        TrieNode* pCrawl = root;
        for (char ch : key) {
            int index = ch - 'a';
            if (!pCrawl->children[index]) {
                return false;
            }
            pCrawl = pCrawl->children[index];
        }
        return (pCrawl != nullptr && pCrawl->isEndOfWord);
    }

    bool startsWith(const std::string& prefix) {
        TrieNode* pCrawl = root;
        for (char ch : prefix) {
            int index = ch - 'a';
            if (!pCrawl->children[index]) {
                return false;
            }
            pCrawl = pCrawl->children[index];
        }
        return true;
    }
};

B. Hàm Z (Z-function)

  1. Định nghĩa: Cho chuỗi S có độ dài n . Mảng Z của S là một mảng z có độ dài n , trong đó z[i] là độ dài của chuỗi con chung dài nhất bắt đầu từ vị trí i của chuỗi S và tiền tố của chính chuỗi S . Nói cách khác, z[i] là độ dài lớn nhất của tiền tố S[0...k-1] sao cho nó bằng với chuỗi con bắt đầu tại i, S[i...i+k-1]. Theo định nghĩa, z[0] thường không xác định hoặc được gán bằng n .

  2. Thuật toán tính Z-function trong thời gian tuyến tính O(|S|) : Thuật toán duyệt qua chuỗi từ trái sang phải để tính z[i].

    • Ý tưởng cốt lõi: Duy trì một "đoạn khớp" [l, r], là đoạn S[l...r] khớp với tiền tố S[0...r-l] có r lớn nhất mà ta đã tìm thấy.
    • Khi tính z[i], nếu i nằm ngoài [l, r], ta tính z[i] một cách "ngây thơ" bằng cách so sánh S[i...] với S[0...] từng ký tự.
    • Nếu i nằm trong [l, r], ta có thể tận dụng thông tin đã tính trước đó. Vị trí i tương ứng với vị trí k = i - l trong tiền tố. Ta biết z[k] là độ dài khớp của S[k...] với tiền tố. Do đó, z[i] ít nhất cũng sẽ bằng z[k], nhưng không được vượt quá phần còn lại của đoạn [l, r] (tức là r - i + 1). Ta có thể khởi tạo z[i] bằng min(z[k], r - i + 1) rồi so sánh tiếp từ đó để mở rộng nếu có thể.
    • Trong quá trình tính toán, ta luôn cập nhật [l, r] nếu tìm được một đoạn khớp mới vươn xa hơn.

  3. Ứng dụng:

    • Tìm kiếm mẫu P trong T: Đây là ứng dụng kinh điển của Z-function, có thể thay thế KMP.
      1. Xây dựng một chuỗi mới S = P + '\#' + T , trong đó # là một ký tự đặc biệt không có trong P và T.
      2. Tính mảng Z cho chuỗi S .
      3. Duyệt qua mảng Z. Nếu tại một vị trí i nào đó (tương ứng với vị trí trong T), ta có z[i] == |P|, điều đó có nghĩa là chuỗi con bắt đầu tại i của S khớp với tiền tố của S (chính là P ) với độ dài |P| . Ta đã tìm thấy một vị trí khớp.
    • Tìm chu kỳ của chuỗi: Nếu n chia hết cho n - z[n-i] thì n-i là một độ dài chu kỳ.
    • Nén chuỗi.

Phần IV: Giới thiệu các chuyên đề Siêu Nâng Cao (Nên biết)

Mục tiêu: Đưa ra cái nhìn tổng quan về các công cụ mạnh nhất trong xử lý chuỗi, định hướng cho các học sinh muốn đi sâu hơn.

  1. Mảng Hậu Tố (Suffix Array):

    • Là gì: Cho một chuỗi S độ dài n , Mảng Hậu Tố là một mảng chứa các chỉ số bắt đầu của tất cả các hậu tố của S (từ 0 đến n-1 ), được sắp xếp theo thứ tự từ điển của các hậu tố đó. Thường đi kèm với Mảng LCP (Longest Common Prefix) giữa hai hậu tố kề nhau trong Mảng Hậu Tố.
    • Làm được gì: Là một cấu trúc dữ liệu cực kỳ mạnh, giải quyết hiệu quả rất nhiều bài toán về chuỗi con (substring):
      • Tìm kiếm một mẫu trong văn bản (nhanh hơn KMP trong một số trường hợp).
      • Tìm chuỗi con chung dài nhất (Longest Common Substring) của nhiều chuỗi.
      • Đếm số chuỗi con khác nhau của một chuỗi.
      • Tìm chuỗi đối xứng dài nhất.
    • Đề cập: Có nhiều thuật toán xây dựng Mảng Hậu Tố. Các thuật toán phổ biến trong lập trình thi đấu có độ phức tạp O(N \\log^2 N) hoặc O(N \\log N) . Cũng có thuật toán xây dựng trong O(N) nhưng rất phức tạp.

  2. Tự Động Hậu Tố (Suffix Automaton):

    • Là gì: Được coi là cấu trúc dữ liệu "tối thượng" về chuỗi con. Nó là một Máy trạng thái hữu hạn đơn định (DFA) nhỏ nhất nhận diện tất cả các chuỗi con của một chuỗi S . Mỗi đường đi trong automaton tương ứng với một chuỗi con của S .
    • Làm được gì: Giải quyết được hầu hết các bài toán mà Mảng Hậu Tố làm được, và nhiều bài toán khác, thường với độ phức tạp tối ưu hơn. Ví dụ: tìm số lần xuất hiện của một mẫu, tìm chuỗi con khác nhau đầu tiên, ...
    • Đề cập: Thuật toán xây dựng online của Suffix Automaton có độ phức tạp thời gian và không gian là O(N) . Tuy nhiên, nó nổi tiếng là một cấu trúc dữ liệu rất phức tạp để hiểu và cài đặt chính xác.

Phần V: Bài Tập Luyện Tập

Nguồn bài tập: VNOI, Codeforces, AtCoder là các nguồn bài tập chất lượng cao.

Chuyên Sơn La Online Judge.
Mã nguồn mở cho giải pháp chấm bài trực tuyến (Online Judge): DMOJ - UOJ - QDUOJ - SYZOJ - OJS - SHARIF - AURORA - CMS