Post

Các thuật toán về xâu kí tự🔐 (Phần 2) (🚧)

Posted Updated
By Nguyễn Minh Tuấn
16 min read
Các thuật toán về xâu kí tự🔐 (Phần 2) (🚧)

Đây là phần 2 của Các thuật toán về xâu kí tự, xem phần 1 ở đây: Các thuật toán về xâu kí tự🔐 (Phần 1)

A. Trie + Trie XOR

I, Trie

1. Khái niệm

Trie là một cấu trúc dữ liệu dạng cây, được thiết kế đặc biệt để lưu trữ và tìm kiếm các xâu ký tự (strings). Điểm đặc biệt của Trie là các xâu có chung tiền tố sẽ chia sẻ chung một đường đi từ gốc xuống.

Tại sao lại cần Trie? (Độ phức tạp)

  • Thay vì tìm kiếm một xâu trong mảng $N$ phần tử mất $\mathcal{O}(N \times len)$ (hoặc $\mathcal{O}(len \log N)$ nếu dùng chặt nhị phân), Trie cho phép chúng ta thêm/xóa/tìm kiếm một xâu chỉ trong độ phức tạp $\mathcal{O}(len)$, với $len$ là độ dài của xâu đó. Khối lượng dữ liệu $N$ hoàn toàn không ảnh hưởng đến tốc độ tìm kiếm.

  • Biến cntPass đếm số xâu đi qua nút $u$, và cntEnd đếm số xâu kết thúc tại $u$. Đây là hai trạng thái cực mạnh cho các bài toán đếm tiền tố.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

struct trie {
    static const int limNode = 1e4 * 55; // tùy vào N và số kí tự
    int nxt[limNode][26]; // node tiếp theo từ node u bằng ký tự c
    int cntEnd[limNode]; // có bao nhiêu string kết thúc tại node u
    int cntPass[limNode]; // có bao nhiêu string đi qua u
    int cnt; // số node hiện tại trong trie
    trie() {
        cnt = 1; // 1-index
        memset(nxt, 0, sizeof nxt);
        memset(cntEnd, 0, sizeof cntEnd);
        memset(cntPass, 0, sizeof cntPass);
    }
    void upd(const string &s) { // cập nhật xâu s vào cây trie
        int u = 1;
        cntPass[u]++;
        for(const char &c: s) {
            int k = c - 'a';
            if(!nxt[u][k]) nxt[u][k] = ++cnt; // nếu chưa có tiền tố c thì cập nhật
            u = nxt[u][k];
            cntPass[u]++;
        }
        cntEnd[u]++;
    }
    bool del(const string &s) { // xóa xâu s ra khỏi cây trie
        // *lưu ý: ktra xâu s tồn tại trong cây trie chưa cái đã, nếu ko thì bị sai do âm
        if(!cntStr(s)) return 0;
        // còn lại là hàm ngược của hàm upd thôi nên có thể copy paste cho lẹ
        int u = 1;
        cntPass[u]--;
        for(const char &c: s) {
            int k = c - 'a'; 
            u = nxt[u][k];
            cntPass[u]--;
        }
        cntEnd[u]--;
        return 1;
    }
    //mấy hàm dưới đây copy paste cho lẹ :v
    int cntStr(const string &s) { // đếm số lượng xâu s trong cây trie
        int u = 1;
        for(const char &c: s) {
            int k = c - 'a';
            if(!nxt[u][k]) return 0;
            u = nxt[u][k];
        }
        return cntEnd[u];
    }
    int cntPre(const string &s) { // đếm số lượng tiền tố s trong cây trie
        int u = 1;
        for(const char &c: s) {
            int k = c - 'a';
            if(!nxt[u][k]) return 0;
            u = nxt[u][k];
        }
        return cntPass[u];
    }
};

Để kiểm tra 1 xâu có tồn tại hay không, ta có thể sử dụng hàm cntStr.

Luôn khai báo Trie ở ngoài hàm main (biến toàn cục) hoặc dùng từ khóa static.

2. Các bài toán kinh điển (Standard Trie)

a, Bài toán 1: Tìm kiếm tiền tố (Dạng cơ bản nhất)

Mô tả: Cho một từ điển $N$ từ. Trả lời $Q$ truy vấn, mỗi truy vấn cho một xâu $P$, hỏi có bao nhiêu từ trong từ điển nhận $P$ làm tiền tố?

Tại sao phải dùng Trie? Nếu dùng Bảng băm, ta chỉ có thể tìm kiếm xâu khớp hoàn toàn. Nếu duyệt trâu thì mất $\mathcal{O}(N \times Q)$. Với Trie, ta chỉ cần gọi hàm CountPrefix(P) trong template là xong trong $\mathcal{O}(|P|)$.

b, Bài toán 2: Điện thoại di động (Auto-complete)

Mô tả: Khi bạn gõ phím, hệ thống cần gợi ý từ dài hơn dựa trên những gì bạn đã gõ. Bài toán yêu cầu tìm từ có thứ tự từ điển nhỏ nhất có tiền tố là $S$.

Giải pháp: Đi theo xâu $S$ xuống một nút $u$ trên Trie. Từ nút $u$, cứ ưu tiên đi xuống nhánh có ký tự nhỏ nhất (a đến z) mà cntPass > 0 cho đến khi gặp cntEnd > 0.

c. Bài toán 3: Quy hoạch động trên Trie (Word Break)

Mô tả: Cho một xâu rất dài $S$ và một bộ từ điển. Hỏi có bao nhiêu cách chia $S$ thành các xâu con sao cho mỗi xâu con đều nằm trong từ điển?

Giải pháp: Gọi $dp[i]$ là số cách chia xâu từ vị trí $i$ đến cuối. Để tính $dp[i]$, thay vì dùng hàm substr và string hashing (rất chậm), ta có thể duyệt từ vị trí $i$ trên xâu $S$, đồng thời đi xuống trên Trie. Nếu tại một nút có cntEnd > 0, ta cộng $dp[i+len]$ vào $dp[i]$. Trie giúp quá trình chuyển trạng thái DP giảm xuống chỉ còn $\mathcal{O}(L_{max})$.

Cách tư duy push dp (forward dp) cực hay chung cho dạng DP + Cây: Ngầm định đồ thị DAG.

Tại mỗi vị trí bắt đầu $i$, bạn đang xây dựng một Đồ thị có hướng không chu trình (DAG):

  • Các nút: Là các vị trí $j$ từ $0$ đến $n-i$ (tượng trưng cho độ dài xâu con).
  • Cạnh: Có một cạnh từ nút $j$ đến nút $j + step$ nếu xâu con của $S$ bắt đầu tại $i+j$ có độ dài $step$ nằm trong tập $T$ (Trie giúp ta tìm tất cả các $step$ này cực nhanh).
  • Mục tiêu: Tìm nút xa nhất (giá trị $j$ lớn nhất) có thể đi tới được từ nút $0$.

Ví dụ: Cho từ điển {“app”, “apple”, “let”} và xâu $S = \text{“apple”}$.

  • Tại $i=0$: Trie tìm được “app” (nhảy tới $i=3$) và “apple” (nhảy tới $i=5$).
  • Tại $i=3$: Trie không tìm thấy từ nào bắt đầu bằng “le…”.
  • Tại $i=5$: Đạt tới cuối xâu -> Kết quả: 5.

II, Trie XOR

1. Khái niệm

Trie XOR là một biến thể của Trie. Thay vì mỗi cạnh là một chữ cái (a - z), thì mỗi cạnh bây giờ là một bit (0 hoặc 1). Một số nguyên sẽ được biểu diễn thành một chuỗi nhị phân có độ dài cố định (thường là 31 bit nếu int hoặc 60 bit nếu long long) và chèn vào Trie từ Bit cao nhất (MSB) xuống Bit thấp nhất (LSB).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

struct trie_xor {
    static const int limNode = 1e5 * 31; // tùy vào N và số bit
    int nxt[limNode][2];
    int cntPass[limNode];
    int cnt;
    trie_xor() {
        cnt = 1;
        memset(nxt, 0, sizeof nxt);
        memset(cntPass, 0, sizeof cntPass);
    }
    // val = 1 để thêm số, val = -1 để xóa số
    void upd(int x, int val) {
        int u = 1;
        cntPass[u] += val;
        for (int i = 30; i >= 0; i--) {
            int k = bit(x, i); // macro bit(mask, i) (mask >> i) & 1 :)
            if (!nxt[u][k]) nxt[u][k] = ++cnt;
            u = nxt[u][k];
            cntPass[u] += val;
        }
    }
    int getMax(int x) {
        int u = 1;
        int res = 0;
        for (int i = 30; i >= 0; i--) {
            int k = bit(x, i);
            // ưu tiên đi nhánh ngược (k^1) nhưng phải còn phần tử
            if (nxt[u][k ^ 1] && cntPass[nxt[u][k ^ 1]] > 0) { // x ^ 1: trick flip bit
                res |= (1 << i); // bật bit thứ i
                u = nxt[u][k ^ 1];
            } else u = nxt[u][k];
            if(!u) return res;
        }
        return res;
    }
};

Ý nghĩa của hàm getMax(int x)

Đây là bản chất của thuật toán Tham lam trên bit:

  • Bit thứ $i$ có giá trị là $2^i$.
  • Tổng tất cả các bit phía sau nó: $2^{i-1} + 2^{i-2} + \dots + 2^0 = 2^i - 1$.

$\Rightarrow$ Kết luận: Nếu tại bit thứ $i$, ta có cơ hội tạo ra bit 1 cho kết quả XOR (bằng cách đi vào nhánh k ^ 1 - nhánh ngược lại với bit hiện tại của $x$), ta BẮT BUỘC phải đi. Một bit 1 ở vị trí $i$ luôn lớn hơn tất cả các bit 1 ở các vị trí phía sau cộng lại

2. Các bài toán kinh điển (Standard Trie)

a, Bài toán 1: Cặp phần tử có XOR lớn nhất (Max XOR Pair)

Mô tả: Cho mảng $A$ gồm $N$ phần tử. Tìm $i, j$ sao cho $A[i] \oplus A[j]$ đạt max. ($N \le 10^5$). Tại sao phải dùng Trie XOR? Duyệt trâu $\mathcal{O}(N^2)$ sẽ bị TLE. Không có thuật toán nào khác tối ưu hơn Binary Trie. Ta nhét lần lượt các số vào Trie XOR, với mỗi số $A[i]$, ta dùng getMax(A[i]) trên các số đã chèn trước đó để cập nhật đáp án. Độ phức tạp $\mathcal{O}(N \times 31)$.

b, Bài toán 2: Đoạn con liên tiếp có XOR lớn nhất (Max XOR Subarray)

Mô tả: Tìm một đoạn con liên tiếp có tổng XOR lớn nhất.

Giải pháp: Dựa vào tính chất $X \oplus X = 0$. Ta xây dựng mảng cộng dồn XOR: $Pref[i] = A[1] \oplus A[2] \dots \oplus A[i]$.

  • Khi đó, XOR của đoạn con từ $L$ đến $R$ là: $Pref[R] \oplus Pref[L-1]$. $\Rightarrow$ Giải theo Bài toán 1 :D
b, Bài toán 3: Số cặp XOR nhỏ hơn $K$ (XOR less than K)

Mô tả: Cho mảng $A$ và số $K$. Đếm số cặp $(i, j)$ sao cho $A[i] \oplus A[j] \le K$.

Giải pháp: Khó hơn getMax một chút. Khi duyệt Trie cùng với một số $X$ để xét các bit của $K$:

  • Nếu bit thứ $i$ của $K$ là 1: Ta có thể đi theo nhánh tạo ra bit 0 cho phép XOR (toàn bộ nhánh này chắc chắn tạo ra số nhỏ hơn $K$, nên ta cộng toàn bộ cntPass của nhánh này vào đáp án), sau đó di chuyển xuống nhánh tạo ra bit 1 để xét tiếp.

  • Nếu bit thứ $i$ của $K$ là 0: Bắt buộc phải đi theo nhánh tạo ra bit 0 cho phép XOR, không được cộng thêm gì cả.

b, Bài toán 4: Max XOR với giới hạn độ dài

Mô tả: Tìm đoạn con có XOR lớn nhất nhưng độ dài đoạn con không được vượt quá $K$ ($R - L + 1 \le K$).

Giải pháp: (Sliding Window + Trie XOR):

  • Khi ta đang ở vị trí $i$, ta cần tìm $P[j]$ trong khoảng $[i-K, i-1]$.
  • Dùng sliding window như sau:
    1. Khi sang vị trí $i$, thêm $P[i-1]$ vào Trie: trie.update(P[i-1], 1).
    2. Nếu $i > K$, xóa $P[i-K-1]$ khỏi Trie: trie.update(P[i-K-1], -1).
    3. Truy vấn trie.getMax(P[i]).

B. Aho–Corasick (KMP trên cây Trie)

C. Suffix Array & Thuật toán Kasai

I. Suffix Array (Mảng hậu tố)

Giả sử ta có xâu $S$ độ dài $N$ (chỉ số từ 1 đến $N$). Một hậu tố bắt đầu tại $i$ là một xâu con kéo dài từ vị trí $i$ đến cuối xâu: $S[i \dots N]$.

Suffix Array ($SA$) là một mảng lưu chỉ số bắt đầu của tất cả $N$ hậu tố của xâu $S$, nhưng các hậu tố này đã được sắp xếp theo thứ tự từ điển.

Một số ứng dụng:

  • Tìm kiếm xâu con: Kiểm tra xâu $P$ có xuất hiện trong $S$ không bằng Chặt nhị phân trên SA trong $O(|P| \log N)$.
  • Đếm số xâu con phân biệt: Tổng số xâu con là $\frac{n(n+1)}{2}$, trừ đi tổng các giá trị trong mảng LCP.
  • Tìm xâu con lặp lại dài nhất: Chính là giá trị lớn nhất trong mảng LCP.
  • Xâu con chung dài nhất của 2 xâu: Nối 2 xâu lại và dựng SA.

Thuật toán xây dựng: Prefix Doubling ($O(N \log^2 N)$)

Cách ngây thơ là dùng sort để so sánh các chuỗi mất $O(N^2 \log N)$. Để tối ưu, chúng ta dùng kỹ thuật nhân đôi tiền tố (Prefix Doubling).

Thay vì so sánh toàn bộ hậu tố, ta so sánh các phần đầu của chúng với độ dài tăng dần theo lũy thừa của 2 ($1, 2, 4, 8, \dots$):

  • Bước 1: Sắp xếp các hậu tố dựa trên 1 ký tự đầu tiên. (thường lấy luôn mã ASCII).
  • Bước 2: Dựa trên kết quả bước 1, sắp xếp dựa trên 2 ký tự đầu tiên.
  • Bước 3: Dựa trên kết quả bước 2, sắp xếp dựa trên 4 ký tự đầu tiên.
  • $\dots$ Tiếp tục nhân đôi ($2^k$) cho đến khi các thứ hạng (rank) phân biệt hoàn toàn.

Việc so sánh 2 hậu tố độ dài $2^k$ thực chất chỉ là so sánh 2 cặp số (rank của $2^{k-1}$ ký tự đầu và rank của $2^{k-1}$ ký tự tiếp theo) $\Rightarrow$ Điều này biến việc so sánh xâu thành so sánh số.

II. Mảng LCP & Thuật toán Kasai ($O(N)$)

Suffix Array bản thân nó chưa đủ mạnh. Ta cần thêm mảng LCP (Longest Common Prefix).

  • $LCP[i]$ lưu độ dài tiền tố chung dài nhất của 2 hậu tố đứng liền kề nhau trong Suffix Array: hậu tố $SA[i]$ và hậu tố $SA[i-1]$.

Ví dụ: “banana”

SA[1] (a) và SA[2] (ana) có LCP là 1 (chung chữ a).

SA[2] (ana) và SA[3] (anana) có LCP là 3 (chung chữ ana).

Tại sao cần thuật toán Kasai?

Nếu tính LCP ngây thơ cho từng cặp sẽ mất $O(N^2)$. Thuật toán Kasai giúp tính mảng này trong $O(N)$ dựa trên một định lý logic toán học cực hay:

Gọi $h[i]$ là độ dài LCP của hậu tố $S[i \dots N]$ với hậu tố đứng ngay trước nó trong $SA$. Khi chuyển sang xét hậu tố $S[i+1 \dots N]$, ta đã bỏ đi 1 ký tự đầu tiên, nên độ dài LCP ít nhất sẽ bị giảm đi 1. Tức là: $h[i] \ge h[i-1] - 1$.

Nhờ tính chất này, thay vì lùi biến so sánh về 0, ta chỉ việc lùi về $k-1$, giúp tổng số bước tăng của vòng lặp không vượt quá $O(N)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

struct suffix_array {
    int n;
    string s;
    vector<int> arr, rank, lcp;
    suffix_array() {}
    suffix_array(const string& s, int n) : s(s), n(n), arr(n + 1), rank(n + 1), lcp(n + 1) {
        FOR(i, 1, n + 1) {
            rank[i] = s[i]; // ban đầu là mã ASCII
            arr[i] = i;
        }
    }
    void build() {
        int m = 256; // kích thước bảng chữ cái ban đầu (ASCII)
        vector<int> cnt(max(n, m) + 1);
        vector<int> tmp_arr(n + 1), tmp_rank(n + 1);
        // bước 1: counting sort theo ký tự đầu tiên
        FOR(i, 1, n + 1) cnt[rank[i] = s[i]]++;
        FOR(i, 1, m + 1) cnt[i] += cnt[i - 1];
        FORd(i, 1, n + 1) arr[cnt[rank[i]]--] = i;
        for (int k = 1; k < n; k <<= 1) {
            // 1. sắp xếp theo nửa sau (vị trí i + k)
            int p = 0;
            // các hậu tố không có nửa sau (độ dài < k) đứng trước
            FOR(i, n - k + 1, n + 1) tmp_arr[++p] = i;
            // các hậu tố còn lại sắp xếp dựa trên vị trí sau khi đã sort ở bước trước
            FOR(i, 1, n + 1) if (arr[i] > k) tmp_arr[++p] = arr[i] - k;
            // 2. sắp xếp theo nửa đầu (vị trí i) bằng Counting Sort
            fill(all(cnt), 0);
            FOR(i, 1, n + 1) cnt[rank[i]]++;
            FOR(i, 1, m + 1) cnt[i] += cnt[i - 1];
            FORd(i, 1, n + 1) arr[cnt[rank[tmp_arr[i]]]--] = tmp_arr[i];
            // 3. Cập nhật lại rank mới
            tmp_rank[arr[1]] = 1;
            p = 1;
            auto get_rank = [&](int idx) {
                return (idx <= n) ? rank[idx] : -1;
            };
            FOR(i, 2, n + 1) {
                // nếu cặp (rank[i], rank[i+k]) giống cặp trước đó thì rank bằng nhau
                if (rank[arr[i]] == rank[arr[i - 1]] && get_rank(arr[i] + k) == get_rank(arr[i - 1] + k))
                    tmp_rank[arr[i]] = p;
                else
                    tmp_rank[arr[i]] = ++p;
            }
            rank = tmp_rank;
            m = p; // thu hẹp bảng chữ cái cho bước sau
            if (p == n) break; // tối ưu: nếu tất cả n hậu tố có rank phân biệt thì dừng sớm
        }

        build_lcp();
    }
    // thuật toán Kasai để tính mảng LCP trong độ phức tạp O(n)
    void build_lcp() {
        int k = 0;
        FOR(i, 1, n + 1) {
            // rank[i] là vị trí của hậu tố i trong mảng arr đã được sắp xếp
            if (rank[i] == n) { // cyclic
                k = 0;
                continue;
            }
            int j = arr[rank[i] + 1]; // j là hậu tố đứng ngay sau i trong Suffix Array
            // đếm số ký tự giống nhau chung của 2 hậu tố
            while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) {
                k++;
            }
            lcp[rank[i]] = k; // lưu kết quả vào mảng lcp
            if (k > 0) k--;   // tối ưu của thuật toán Kasai: hậu tố tiếp theo sẽ có lcp ít nhất là k-1
        }
    }
};

D. Suffix Automaton (SAM)

data structure, string, template
hash
This post is licensed under CC BY 4.0 by the author.