Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Cấu trúc dữ liệu: Trie (cây tiền tố)

  1. #1
    Ngày gia nhập
    09 2015
    Bài viết
    6

    Mặc định Cấu trúc dữ liệu: Trie (cây tiền tố)

    1. Giới thiệu
    Cho 1 bài toán sau:
    Cho tập A gồm n xâu kí tự, sau đó cho một xâu s. Hỏi xem bên trong A tồn tại bao nhiêu xâu s?
    Bài này có thể giải một cách đơn giản như sau:
    C++ Code:
    1. #include <bits/stdc++.h>
    2.  
    3. using namespace std;
    4. const int maxn = 100000;
    5.  
    6.     map<string, int> mp;
    7.     int n;
    8.     string a[maxn], s;
    9.  
    10. int main() {
    11.     cin >> n;
    12.     for (int i = 1; i <= n; i++) {
    13.         cin >> a[i];
    14.         mp[a[i]]++;
    15.     }
    16.     cin >> s;
    17.     cout << mp[s];
    18.     return 0;
    19. }
    bằng cách sử dụng map thì ta có thể dễ dàng giải được bài tập này, nhưng nếu đề bài sửa lại thành đếm xem có bao nhiêu từ bắt đầu bằng s thì sao
    Khi đó ta cần dùng đến Trie.
    2. Trie là gì?
    đơn giản chỉ là một cái cây dùng để lưu "từ", hay còn gọi là từ điển, lưu như sau:
    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		i1.png
Lần xem:	0
Size:		13.3 KB
ID:		37350
    3. Cài đặt
    Tạo ra 1 class Trie:
    C++ Code:
    1. class Trie {
    2.  
    3. }
    Thứ nhất, Trie là cây, mà cây thì phải có nút:
    C++ Code:
    1.         struct node {
    2.             int num, index, w_count;
    3.             int child[26];
    4.         };
    trong đó, index là địa chỉ của node, num là số từ đi qua node đó lúc insert, w_count là số từ kết thúc tại node đó, child là mảng lưu địa chỉ tới con của node đó, child[26] nghĩa là 26 chữ cái ấy mà, ở đây mình dùng bảng chữ cái 'a' -> 'z' (nói hơi khó hiểu một chút, tí nữa xem code là hiểu ngay ấy mà )
    Khởi tạo và phá bỏ cây:
    C++ Code:
    1.         vector<node> tree;
    2.         inline void new_node() {
    3.             node aw;
    4.             aw.num = 0;
    5.             for (int i = 0; i < 10; i++) aw.child[i] = -1;
    6.             aw.index = tree.size();
    7.             tree.push_back(aw);
    8.         }
    9.         inline void destruct() {
    10.             tree.clear();
    11.         }
    12.  
    13.         inline void init() {
    14.             new_node();
    15.         }
    Khởi tạo gốc là node rỗng tương đương với việc cho xâu "" vào trong cây (xâu rỗng đấy không phải dấu cách)
    Nếu vẫn chưa hiểu tại sao mà khởi tạo cây mà lại new_node() thì xem lại hình ở mục 2 =))
    Thao tác thêm từ vào cây (add_word):
    C++ Code:
    1.         inline void add_word(const string& s) {
    2.             int w;
    3.             int indx = 0;
    4.             for (int i = 0; i < s.size(); i++) {
    5.                 tree[indx].num++;
    6.                 w = s[i] - 'a';
    7.                 if (tree[indx].child[w] == -1) {
    8.                     new_node();
    9.                     tree[indx].child[w] = tree.size() - 1;
    10.                 }
    11.                 indx = tree[indx].child[w];
    12.             }
    13.             tree[indx].num++;
    14.             tree[indx].w_count++;
    15.         }
    Thao tác đếm xem có bao nhiêu từ bắt đầu bởi s (count_pref):
    C++ Code:
    1.         inline int count_pref(const string& s) {
    2.             int w;
    3.             int indx = 0;
    4.             for (int i = 0; i < s.size(); i++) {
    5.                 w = s[i] - 'a';
    6.                 if (tree[indx].child[w] == -1) return 0;
    7.                 indx = tree[indx].child[w];
    8.             }
    9.             return tree[indx].num;
    10.         }
    Tương tự, đếm xem có bao nhiêu xâu s trong dãy cũng như vậy (count_word):
    C++ Code:
    1.         inline int count_word(const string& s) {
    2.             int w;
    3.             int indx = 0;
    4.             for (int i = 0; i < s.size(); i++) {
    5.                 w = s[i] - 'a';
    6.                 if (tree[indx].child[w] == -1) return 0;
    7.                 indx = tree[indx].child[w];
    8.             }
    9.             return tree[indx].w_count;
    10.         }
    Thao tác xóa xâu khỏi cây (del_word): y như thêm vào thôi
    C++ Code:
    1.         inline void del_word(const string& s) {
    2.             if (!count_pref(s)) return; // không có thì xóa làm gì mất công =))
    3.             int w;
    4.             int indx = 0;
    5.             for (int i = 0; i < s.size(); i++) {
    6.                 tree[indx].num--;
    7.                 w = s[i] - 'a';
    8.                 indx = tree[indx].child[w];
    9.             }
    10.             tree[indx].num--;
    11.             tree[indx].w_count--;
    12.         }
    4. Ứng dụng
    Để làm công cụ tìm kiếm thôi =)). VD như:
    http://vdict.com/
    hay http://kissanime.com/
    . . . . . vv
    5. Một số bài tập =))
    http://www.spoj.com/PTIT/problems/BCTELEPH/
    https://open.kattis.com/problems/phonelist
    Nói trước, 2 bài này là 1 nhá =))

  2. #2
    Ngày gia nhập
    10 2018
    Bài viết
    2

    a. Cho n xâu kí tự hỏi có tồn tại xâu nào là tiền tố của xâu nào không?
    b. Cho n số điện thoại gồm các chữ số từ 0 đến 9 hỏi có số nào là tiền tố của các số còn lại không
    giup em bai nay voi sử dụng cậy tiền tố ạ :((

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn