vi
new
+3
Avatar
Viblo Algorithm @algorithm
8.9K 674 107
Đã đăng vào thg 3 22, 9:00 SA 14 phút đọc
313

Trie Tree (phần 1) - Xử lý xâu kí tự

I. Giới thiệu chung

Trie là một cấu trúc dữ liệu dạng cây, hay còn gọi là Cây tiền tố (Suffix tree). Đây là một cấu trúc dữ liệu hữu ích sử dụng để quản lý một tập hợp các xâu kí tự, và có thể mở rộng ra các bài toán liên quan tới quản lý tập số nguyên (xem phần 2 của bài viết tại đây).

Cấu trúc của Trie rất đơn giản, nó là một cây kiểm soát các kí tự của một xâu trên từng cạnh, cho phép lưu trữ các xâu có tiền tố giống nhau rất hiệu quả.

Trên Trie Tree, mỗi đường đi từ gốc tới lá sẽ biểu thị một xâu được tạo thành bởi các kí tự trên các cạnh của đường đi đó. Những xâu có chung tiền tố sẽ có chung một phần đường đi trên cây, chẳng hạn như trong hình vẽ trên, đường đi từ đỉnh 00 tới đỉnh 1313 biểu thị xâu caaa, còn đường đi từ đỉnh 00 tới đỉnh 1212 biểu thị xâu cba.

Để cài đặt được Trie Tree, ta chỉ cần xây dựng một cấu trúc child(u,c)=vchild(u, c) = v với ý nghĩa: Nút con của uu là vv và cạnh giữa chúng biểu diễn kí tự c,c, hoặc v=−1v = -1 nếu như uu là nút lá. Ví dụ trong hình vẽ trên: child(0, b) = 2, child(3, a) = 7,... Như vậy ta chỉ cần duy trì một mảng child[26]child[26] với mỗi đỉnh uu để biểu diễn Trie, và xâu tạo thành từ các cạnh trên đường đi từ đỉnh gốc tới đỉnh uu sẽ gọi là xâu thể hiện bởi đỉnh uu.

II. Cài đặt Trie và ứng dụng

1. Phương pháp

Với mục đích giải quyết tốt các bài tập, Trie được cài đặt để hỗ trợ 33 thao tác sau với độ phức tạp tuyến tính

  • Thêm xâu vào tập hợp.
  • Xóa một xâu khỏi tập hợp.
  • Kiểm tra một xâu có nằm trong tập hợp hay không?

Do vậy, ngoài mảng child,child, ta cần sử dụng thêm hai biến (tùy vào bài toán có thể bỏ đi):

  • existexist: Có bao nhiêu xâu là xâu được thể hiện bởi đỉnh uu.
  • cntcnt: Có bao nhiêu xâu có tiền tố là xâu được thể hiện bởi đỉnh uu.

Tức là một đỉnh của cây giờ có dạng (child[26],exist,cnt)\big(child[26], exist, cnt\big). Sau đây ta sẽ nghiên cứu cách cài đặt các thao tác của Trie.

Thao tác thêm xâu

Bắt đầu từ đỉnh gốc, ta duyệt lần lượt qua các kí tự trong xâu và đi xuống cạnh chứa kí tự tương ứng. Nếu như cạnh tương ứng đó chưa tồn tại thì ta tạo đỉnh mới rồi thêm nó vào mảng childchild. Dưới đây là hình ảnh minh họa Trie với tập hợp các xâu aa, aba, ba, caaa, cab, cba, ca.

<center>

Hình ảnh minh họa tham khảo từ VNOI

</center>

Thao tác xóa xâu

Đầu tiên ta kiểm tra xem xâu cần xóa có tồn tại trong Trie hay không, nếu có nhiều xâu như vậy, ta giảm giá trị existexist của đỉnh tương ứng với xâu đó đi 11 đơn vị. Nếu không, ta sẽ đệ quy từ dưới lên trên để xóa các đỉnh dư thừa.

Thao tác tìm xâu

Gần giống với thao tác thêm xâu, chỉ khác là nếu không có cạnh tương ứng với kí tự đang duyệt, ta dừng ngay lập tức vì xâu đó sẽ không thể xuất hiện trong Trie. Sau khi duyệt xong ta kiểm tra ở đỉnh đó có xâu nào kết thúc hay không (tức là kiểm tra exist≠0exist \ne 0).

2. Kĩ thuật cài đặt

Có hai cách cài đặt Trie là cài đặt bằng mảng hoặc cài đặt bằng con trỏ (hay còn gọi là Trie động). Dưới đây tôi sẽ trình bày cả hai cách, tuy nhiên lời khuyên là các bạn nên cài đặt bằng con trỏ, bởi vì ba lí do dưới đây:

  • Không cần tính toán bộ nhớ mảng, tránh lãng phí dữ liệu.
  • Dễ dàng cài đặt nhiều Trie một lúc bằng cách tạo một gốc mới khi cần một Trie mới.
  • Có thể xóa một nút không cần thiết nữa trên Trie.

Các cài đặt trong bài viết này được tham khảo từ trang web VNOI, chỉ chỉnh sửa lại format code một chút nhằm dễ nhìn hơn.

Cài đặt bằng mảng

const int max_nodes = ...;

struct Trie
{
    struct Node
    {
        int child[26];
        int exist, cnt;
    } nodes[max_nodes];

    int cur = 0; // Hiện trong trie đang có bao nhiêu đỉnh.
    
    // Tạo nút gốc cho Trie là đỉnh 0 khi khởi tạo Trie.
    Trie() : cur(0) 
    {   
        memset(nodes[0].child, -1, sizeof(nodes[cur].child));
        nodes[0].exist = nodes[0].cnt = 0;
    };
    
    // Tạo và trả về giá trị của đỉnh mới được tạo ra.
    int new_node() 
    { 
        ++cur;
        memset(nodes[cur].child, -1, sizeof(nodes[cur].child));
        nodes[cur].exist = nodes[cur].cnt = 0;
        
        return cur;
    }

    void add_string(string s) 
    {
        int pos = 0;
        for (auto f : s) 
        {
            int c = f - 'a';
            // Nếu cạnh tương ứng chữ cái c chưa tồn tại thì ta tạo ra đỉnh mới.
            if (nodes[pos].child[c] == -1)
                nodes[pos].child[c] = new_node();
            
            // Có thêm một xâu trong trie có tiền tố là xâu được thể hiện 
            // bằng đỉnh hiện tại.
            pos = nodes[pos].child[c];
            ++nodes[pos].cnt; 
        }
        
        // Đã tìm được đỉnh tương ứng với xâu s, ta tăng biến exist của đỉnh lên 1.
        ++nodes[pos].exist; 
    }
    
    // Trả về liệu đỉnh pos có thể bị xóa đi hay không, đồng thời xóa xâu s nếu có thể. 
    bool delete_string_recursive(int pos, string& s, int i) 
    { 
        // Nếu chưa đến đỉnh tương ứng với xâu s thì tiếp tục đệ quy xuống dưới.
        if (i != (int) s.size()) 
        { 
            int c = s[i] - 'a';
            bool is_child_deleted = delete_string_recursive(nodes[pos].child[c], s, i + 1);
            // Nếu đỉnh con tương ứng bị xóa thì ta gán lại đỉnh tương ứng bằng -1.
            if (is_child_deleted)
                nodes[pos].child[c] = -1;
        }
        // Nếu đã đến đỉnh tương ứng với xâu s thì ta giảm biến exist của đỉnh đi 1
        else 
            --nodes[pos].exist; 
        
        // Nếu đỉnh đang xét không phải gốc thì ta giảm biến cnt của đỉnh đi 1
        // và kiểm tra đỉnh có bị xóa đi hay không?
        // Đỉnh bị xóa nếu không còn xâu nào đi qua nó, nói cách khác là
        // không còn xâu nào có tiền tố là xâu được thể hiện bởi đỉnh pos.
        if (pos != 0) 
        { 
            --nodes[pos].cnt;
            
            if (nodes[pos].cnt == 0) 
                return true;
        }
        
        return false;
    }

    void delete_string(string s) 
    {
        // Kiểm tra xâu s có trong Trie hay không.
        if (find_string(s) == false) 
            return; 
        
        // Gọi hàm đệ quy xóa xâu s khỏi Trie.
        delete_string_recursive(0, s, 0); 
    }

    // Tìm xâu s trong Trie. 
    bool find_string(string s) 
    {
        int pos = 0;
        for (auto f: s) 
        {
            int c = f - 'a';
            if (nodes[pos].child[c] == -1) 
                return false;
            
            pos = nodes[pos].child[c];
        }
        
        // Kiểm tra có xâu nào kết thúc tại đỉnh này hay không.
        return (nodes[pos].exist != 0); 
    }
};

Cài đặt bằng con trỏ

Mặc dù có nhiều ưu điểm, nhưng cài đặt bằng con trỏ cũng rất dễ gây ra nhầm lẫn nếu các bạn chưa vững kiến thức về cấp phát bộ nhớ động. Vì thế, trước khi quyết định sử dụng con trỏ để cài đặt Trie, hãy xem lại các kiến thức dưới đây:

Các phần trong code có chức năng tương tự như cách cài đặt bằng mảng nên sẽ không chú thích lại!

struct Trie
{
    struct Node
    {
        Node* child[26];
        int exist, cnt;

        Node() 
        {
            for (int i = 0; i < 26; i++) 
                child[i] = NULL;
            
            exist = cnt = 0;
        }
    };
 
    int cur;
    Node* root;
    Trie() : cur(0)
    {
        root = new Node();
    };
 
    void add_string(string s) 
    {
        Node* p = root;
        for (auto f: s) 
        {
            int c = f - 'a';
            if (p -> child[c] == NULL) 
                p -> child[c] = new Node();

            p = p -> child[c];
            p -> cnt++;
        }
        
        p -> exist++;
    }

    bool delete_string_recursive(Node* p, string& s, int i) 
    {
        if (i != (int) s.size()) 
        {
            int c = s[i] - 'a';
            bool is_child_deleted = delete_string_recursive(p -> child[c], s, i + 1);
            if (is_child_deleted) 
                p->child[c] = NULL;
        }
        else 
            p -> exist--;

        if (p != root) 
        {
            p -> cnt--;
            if (p -> cnt == 0) 
            {
                // Khác với cài đặt bằng mảng, ta có thể thực sự xóa đỉnh này đi.
                delete(p); 
                
                return true;
            }
        }
        return false;
    }
 
    void delete_string(string s) 
    {
        if (find_string(s) == false) 
            return;

        delete_string_recursive(root, s, 0);
    }
 
    bool find_string(string s) 
    {
        Node* p = root;
        for (auto f: s) 
        {
            int c = f - 'a';
            if (p -> child[c] == NULL) 
                return false;
            
            p = p -> child[c];
        }
        
        return (p -> exist != 0);
    }
};

III. Các ứng dụng cơ bản

1. Sắp xếp danh sách các xâu

Thông qua Trie Tree, ta có thể đạt được một thuật toán để sắp xếp một danh sách nn xâu theo thứ tự từ điển tăng dần chỉ trong thời gian tuyến tính.

Sau khi xây dựng Trie gồm các xâu trong danh sách, ta sử dụng DFS\text{DFS} để duyệt Trie đó, đi lần lượt các cạnh theo thứ tự chữ cái tăng dần. Duyệt tới một đỉnh tới bất kì, ta sẽ in ra các xâu được thể hiện bởi đỉnh đó nếu có. Dễ thấy ta sẽ lần lượt thu được các xâu trong danh sách theo thứ tự từ điển tăng dần.

void dfs(int pos, string& current_string, vector < string >& res) 
{
    for (int i = 1; i <= nodes[pos].exist; ++i) 
        res.push_back(current_string);

    for (int i = 0; i < 26; ++i) 
        if (nodes[pos].child[i] != -1) 
        {
            current_string += char(i + 'a');
            dfs(nodes[pos].child[i], current_string, res);
            current_string.pop_back();
        }
}

vector < string > sort_strings() 
{
    string current_string = "";
    vector < string > res;
    dfs(0, current_string, res);
    
    return res;
}

Độ phức tạp trung bình của cách làm này sẽ là O(m×n)O(m \times n) với mm là độ dài trung bình của các xâu. Như vậy, nếu độ dài các xâu nhỏ và danh sách lại gồm nhiều xâu thì cách làm này sẽ có ưu thế hơn so với những thuật toán sắp xếp truyền thống Quicksort hay Mergesort. Và điều quan trọng là Trie có thể hỗ trợ cả các thao tác thêm - xóa - tìm kiếm xâu chỉ trong O(m),O(m), nên tùy vào yêu cầu bài toán ta có thể lựa chọn cách tiếp cận phù hợp.

2. Truy vấn tiền tố chung dài nhất của hai xâu

Với một danh sách nn xâu, Trie Tree có thể hỗ trợ trả lời truy vấn tìm độ dài tiền tố chung dài nhất giữa hai xâu bất kì trong danh sách.

Đầu tiên, ta thêm tất cả các xâu trong danh sách vào Trie.

Với hai xâu bất kì trong danh sách, ta có thể thấy tiền tố chung của chúng cũng có thể được thể hiện bằng một đỉnh trong Trie. Tìm tiền tố chung dài nhất nghĩa là đi tìm một đỉnh mà từ vị trí đó, hai xâu bắt đầu tách ra hai nhánh khác nhau (khoảng cách tới gốc xa nhất). Dễ nhận thấy, đỉnh biểu thị tiền tố chung dài nhất của hai xâu chính là Nút cha chung gần nhất của hai đỉnh này. Từ đây ta có thể đưa về bài toán LCA trên cây.

Lời giải bài toán LCA các bạn hãy tham khảo lại tại đây.

Code mẫu

#include <bits/stdc++.h>

using namespace std;

struct Trie 
{
    struct Node 
    {
        Node* child[26];
        int index;
        Node () 
        {
            for (int i = 0; i < 26; ++i) 
                child[i] = NULL;

            index = 0;
        }
    };

    Node* root;
    vector < vector < int > > f;
    vector < int > lv;
    vector < int > leaf;
    int max_log;
    int cnt;

    Trie () {}

    Trie(int total_node) 
    {
        root = new Node();
        f.resize(total_node + 5);
        lv.assign(total_node + 5, 0);
        leaf.assign(total_node + 5, 0);
        max_log = log2(total_node + 1);

        for (int i = 0; i <= total_node; ++i)
            f[i].assign(max_log + 1,0);
        
        cnt = 0;
    }

    void add(string s, int id) 
    {
        Node* tmp = root;
        for (int i = 0; i < (int) s.size(); ++i) 
        {
            int c = s[i] - 'a';
            if (tmp -> child[c] == NULL) 
            {
                tmp -> child[c] = new Node();
                tmp -> child[c] -> index = ++cnt;
                f[cnt][0] = (tmp -> index);
                lv[cnt] = i+1;
                for (int j = 1; j <= max_log; ++j) 
                    f[cnt][j] = f[f[cnt][j - 1]][j - 1];
            }

            tmp = tmp -> child[c];
        }

        leaf[id] = cnt;
    }

    int lca (int u, int v) 
    {
        if (lv[u] < lv[v]) 
            swap(u, v);

        for (int j = max_log; j >= 0; --j)
            if (lv[f[u][j]] >= lv[v]) 
                u = f[u][j];
        
        for (int j = max_log; j >= 0; --j) 
            if (f[u][j] != f[v][j]) 
            {
                u = f[u][j];
                v = f[v][j];
            }
        
        while (u != v) 
        {
            u = f[u][0];
            v = f[v][0];
        }

        return u;
    }

    int max_pref(int u, int v) 
    {
        return lv[lca(leaf[u], leaf[v])];
    }
} Tree;


signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int q; 
    cin >> q;

    int cnt = 0;
    Tree = Trie(5e4);

    while (q--) 
    {
        int t; 
        cin >> t;
        if (t == 1) 
        {
            string s; 
            cin >> s;

            Tree.add(s,++cnt);
        }
        else 
        {
            int u, v; 
            cin >> u >> v;

            cout << Tree.max_pref(u, v) << endl;
        }
    }

    return 0;
}

3. Truy vấn tìm xâu có thứ tự từ điển thứ k

Trong một danh sách gồm nn xâu, Trie Tree có thể hỗ trợ truy vấn tìm xâu có thứ tự từ điển lớn thứ kk với ý tưởng xây dựng xâu đáp án lần lượt từng kí tự từ trái qua phải.

Đầu tiên ta dựng Trie chứa tất cả các xâu trong danh sách ban đầu. Xuất phát từ đỉnh gốc, ở đỉnh hiện tại đang xét, ta sử dụng biến đếm cntcnt ở mỗi đỉnh con để xác định kí tự tiếp theo của xâu đáp án là gì. Sau đó di chuyển xuống đỉnh con đó để tiếp tục tìm kí tự tiếp theo.

Code mẫu

string find_kth_string(int k) 
{
    int pos = 0;
    string res = "";
    while (true) 
    {
        if (nodes[pos].exist >= k) 
            break;
        
        k -= nodes[pos].exist;

        for (int i = 0; i < 26; i++) 
            if (nodes[pos].child[i] != -1) 
            {
                int nxt = nodes[pos].child[i];
                if (nodes[nxt].cnt >= k) 
                {
                    res += char(i + 'a');
                    pos = nxt;
                    break;
                }
                
                k -= nodes[nxt].cnt;
            } 
    }

    return res;
}

IV. Một số bài tập khác

1. FSTR

Đề bài

Bờm viết một chương trình hỗ trợ học ngoại ngữ. Module quản lí từ vựng với phép tìm kiếm từ được Bờm xây dựng theo quy trình: Giả sử danh sách từ chương trình đang có là w1,w2,...,wN,w_1, w_2,..., w_N, mỗi khi nhận được mẫu tìm kiếm P,P, chương trình sẽ lần lượt so sánh PP với w1,w2,...w_1, w_2,... cho đến khi gặp từ trùng với PP hoặc đã hết danh sách từ. Khi so sánh PP với các từ, chương trình sẽ lần lượt so sánh các kí tự từ trái qua phải cho đến khi gặp kí tự sai khác hay một trong hai từ kết thúc (khi đó nếu cả hai từ cùng kết thúc là tìm kiếm thành công).

Để khảo sát hiệu năng của module tìm kiếm, Bờm xây dựng một danh sách NN từ và thực hiện tìm kiếm QQ mẫu, với mỗi mẫu Bờm cần xác định số thao tác cơ sở mà chương trình thực hiện, thao tác cơ sở là một lần so sánh kí tự hoặc một lần xử lí khi gặp kết thúc từ. Số thao tác cơ sở thực hiện với mỗi mẫu tìm kiếm sẽ bằng tổng của: Số lượng từ được so sánh với mẫu và độ dài của tiền tố chung dài nhất của mỗi từ với mẫu.

Yêu cầu: Hãy giúp Bờm thực hiện việc khảo sát trên mà không cần thực hiện chương trình của Bờm?

Ý tưởng

Ta xử lý offline các truy vấn.

Với mỗi mẫu tìm kiếm gọi posipos_i là vị trí nhỏ nhất sao cho w1...posiw_{1...pos_i} bằng với mẫu tìm kiếm đó (có thể cài đặt bước này bằng map, chặt nhị phân, Trie Tree,...). Ở đây ta sẽ sử dụng Trie vì mục đích luyện tập.

Sắp xếp lại các mẫu tìm kiếm theo posipos_i.

Xử dụng hai con trỏ, khi duyệt đến mẫu tìm kiếm thứ ii ta thêm dần các wjw_j với j≤posij \leq pos_i vào Trie.

Kết quả của mỗi truy vấn có thể tính thông qua Trie như đoạn code dưới đây:

int find(string s)
{
    int pos = 0, ans = 0;
    for (auto ch : s)
    {
        int i = ch - 'a';

        if (trie[pos].child[i] == -1)
            return 0;

        pos = trie[pos].child[i];
        ans += trie[pos].cnt;
    }

    return ans;
}

Độ phức tạp: O(n+m),O(n + m), với mm là tổng độ dài các xâu.

Code mẫu

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 30050;
int res[maxn];
string s[maxn], t[maxn];

struct Node 
{
    Node* child[26];
    vector < int > v;
    int cost;

    Node() 
    {
        for (int i = 0; i < 26; ++i)
            child[i] = NULL;

        cost = 0;
    }
};

struct Trie 
{
    Node* root;

    Trie()
    {
        root = new Node();
    }

    void add(string s, int id) 
    {
        Node* p = root;
        for (int i = 0; i < s.size(); ++i) 
        {
            int c = s[i] - 'a';
            if (p -> child[c] == NULL)
                p -> child[c] = new Node();

            p = p -> child[c];
        }

        p -> v.push_back(id);
    }
};

void process(Trie* root, string s) 
{
    Node* p = root -> root;
    int cur = 0;
    for (int i = 0; i < s.size(); ++i) 
    {
        int c = s[i] - 'a';
        p -> cost++;
        cur += p -> cost;

        if (p -> child[c] == NULL) 
            return; 

        p = p -> child[c];
    }

    p -> cost++; 
    cur += p -> cost;

    vector < int > v = p -> v;
    for (int i = 0; i < v.size(); ++i)
        res[v[i]] = cur;

    p -> v.clear();
}

void cal(Node* u, int cost) 
{
    for (int i = 0; i < u -> v.size(); ++i) 
        res[u -> v[i]] = cost;

    for (int i = 0; i < 26; ++i) 
    {
        if (u -> child[i] == NULL) 
            continue;

        cal(u -> child[i], u -> child[i] -> cost + cost);
    }
}

void solution(Trie* root, int n, int q) 
{
    memset(res, 0, sizeof(res));

    for (int i = 1; i <= n; ++i) 
        process(root, s[i]);

    cal(root -> root, root -> root -> cost);

    for (int i = 1; i <= q; ++i) 
        cout << res[i] << '\n'; 
}

signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; ++i) 
        cin >> s[i];

    Trie* root = new Trie();
    for (int i = 1; i <= q; ++i) 
    {
        cin >> t[i];
        root -> add(t[i], i);
    }

    solution(root, n, q);

    return 0;
}

2. Perfect Matching

Đề bài

Một lớp học nọ có nn học sinh, tên của học sinh thứ ii được biểu diễn bằng một chuỗi kí tự sis_i.

Có nn biệt danh cũng được biểu diễn bằng các chuỗi kí tự pip_i.

Ta kí hiệu lcp(a,b)lcp(a,b) là độ dài tiền tố chung dài nhất giữa hai xâu aa và bb.

Bạn có thể chọn cc là dãy hoán vị từ 11 tới n,n, tương đương với việc gán cho bạn thứ ii biệt danh là pcip_{c_i}. Cách chọn này có độ "hoàn hảo" là ∑lcp(si,pci);∀i∈[1,n]\sum lcp(s_i,p_{c_i}); \forall i \in[1,n].

Yêu cầu: Hãy tìm dãy hoán vị cc có độ hoàn hảo lớn nhất?

Ý tưởng

Tóm tắt

Cho hai tập xâu AA và BB đều có nn phần tử, tìm cách ghép nn cặp xâu si,ti (s∈A,t∈B)s_i, t_i \ (s \in A, t \in B) sao cho tổng ∑i=1nlcp(si,ti)\sum^n_{i = 1}lcp(s_i, t_i) là lớn nhất.

Hướng giải

Bài này ta có thể giải bằng cách DFS\text{DFS} trên cây Trie. Đầu tiên, ta cho hết các xâu thuộc tập AA và BB vào trong cây. Gọi xx là nút ta đang thực hiện DFS,\text{DFS}, h(x)h(x) là khoảng cách từ nút gốc đến x,cntA(x),cntB(x)x, cnt_A(x), cnt_B(x) lần lượt là số xâu thuộc tập AA và tập BB mà đi qua nút này.

Nhận xét: Khi hai xâu s,ts, t đều đi qua một nút xx trong cây Trie, thì lcp(s,t)≥h(x)lcp(s, t) \ge h(x). Nhận xét này chính từ cách hoạt động của Trie là gộp các xâu có cùng tiền tố.

Từ đây ta có thuật toán tham lam như sau: DFS\text{DFS} từ gốc của Trie, sau đó đi tới nút sâu nhất có thể thỏa mãn có ít nhất một xâu thuộc tập AA và một xâu thuộc tập B,B, sau đó ghép chúng thành min(cntA(x),cntB(x))\text{min}\big(cnt_A(x), cnt_B(x)\big) cặp có lcp=h(x)lcp = h(x). Cuối cùng cộng vào nút cha các xâu chưa được ghép cặp để khi kết thúc DFS\text{DFS} ta sẽ quay lại ghép tiếp.

Độ phức tạp: O(n+m)O(n + m).

Code mẫu

#include <bits/stdc++.h>

using namespace std;

// Cấu trúc một Node trên Trie. Ở code này cài riêng ra ngoài chứ không lồng vào Trie, để 
// khi DFS vẫn khai báo được tham số kiểu Node*. 
struct Node
{
    Node* child[26];
    vector < int > v[2]; // v[0] lưu chỉ số của n xâu tên đầu, v[1] lưu chỉ số của n xâu biệt danh sau.

    Node()
    {
        for (int i = 0; i < 26; ++i)
            child[i] = NULL;
    }
};

struct Trie
{
    // Con trỏ trỏ vào Node gốc của 1 Trie khi tạo ra.
    Node* root;

    Trie()
    {
        root = new Node();
    }

    void add(string s, int id, int pos)
    {
        Node* p = root;
        for (int i = 0; i < (int) s.size(); ++i)
        {
            int c = s[i] - 'a';
            if (p -> child[c] == NULL)
                p -> child[c] = new Node();

            p = p -> child[c];
        }

        p -> v[pos].push_back(id);
    }
};

int res = 0;

void dfs(Node* u, int depth)
{
    for (int i = 0; i < 26; ++i)
    {
        if (u -> child[i] == NULL)
            continue;

        dfs(u -> child[i], depth + 1);

        vector < int > cop = u -> child[i] -> v[0];
        for (int i = 0; i < (int) cop.size(); ++i)
            u -> v[0].push_back(cop[i]);

        cop = u -> child[i] -> v[1];
        for (int i = 0; i < (int) cop.size(); ++i)
            u -> v[1].push_back(cop[i]);
    }

    res += depth * min(u -> v[0].size(), u -> v[1].size());

    while (u -> v[0].size() && u -> v[1].size())
    {
        u -> v[0].pop_back();
        u -> v[1].pop_back();
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    Trie* root = new Trie();
    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;
        root -> add(s, i, 0);
    }

    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;

        root -> add(s, i, 1);
    }

    dfs(root -> root, 0);

    cout << res;
}

V. Tài liệu tham khảo

Để tiếp tục xem phần thứ 22 của bài viết, mời các bạn nhấn vào đây.

Competitive Programming Data Structures tree

All rights reserved

Mục lục


Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí