trie.cpp

Trie - Lưu giá trị tương ứng với xâu

Bài toán

Mọi người muốn mua xe và đăng ký biển số xe. Khi một người tên là xxx đến phòng đăng kí, nếu ông xxx đã đăng kí biến số xe thì nói cho ông ấy biết biển số xe của ông ấy, nếu ông ấy chưa có biển số xe thì cập cho ông ấy một biển số xe. (Coi biển số xe là một số nguyên)

Rất nhiều bài đồ thị cho mạng lưới các thành phố và danh sách đường đi. Chúng ta rất cần mã hóa tên các thành phố này thành số để tiện xử lý.

Độ phức tạp

đọc và gán : O(m) với m là độ dài tên của ông xxx

Sample Input

DDat

TuanGay

DDat

LinhChoCon

Sample Output

1

2

1

3

trie.cpp

#include <stdio.h>

#include <vector>

using namespace std;

// trie

class trie {

  public :

    struct node {

        int a[64];

        int value;

        int& operator[] (int i){ return a[i%64]; }

        node() { for (int i=0; i<64; i++) a[i]=0; value=0; }

    };

    vector <node> a;

    int& operator[] (char *s){

        int pos=0, i, c;

        for (i=0; c=s[i]; i++)

        {

            if (a[pos][c]==0) {

                a.push_back(node());

                a[pos][c] = a.size()-1;

            }

            pos=a[pos][c];

        }

        return a[pos].value;

    }

    void clear(){ a.clear(); a.push_back(node()); }

    trie(){ clear(); }

};

trie tr;

// main

main(){

    int cnt=0;

    char s[2309];

    for(;;){

        gets(s);

        if (tr[s]==0) tr[s]=++cnt;

        printf("%s = %d\n", s, tr[s]);

    }   

}

Nhận xét

Khá ngắn gọn và dễ nhớ, rất hiệu quả, nhanh hơn rất nhiều so với việc dùng map và an toàn hơn việc hash.