Trie

Đề bài: http://www.spoj.com/problems/DICT/

Code C++:

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

struct node {
    bool w = false;
    int next[26];
};
node trie[700000];
int t = 0;
string p;
string rest;

void insert( const string & word ) {
    int node = 0;
    for(int i = 0; i < word.size(); i++) {
        int letter = (word[i] - 'a');
        trie[node].next[letter] = trie[node].next[letter] ? trie[node].next[letter] : ++t;
        node = trie[node].next[letter];
    }
    trie[node].w = true;
}

void dfs(int node) {
    if ( trie[node].w && rest.size() ) cout << p + rest << '\n';
    for(int i = 0; i < 26; i++) {
        if (trie[node].next[i]) {
            rest.push_back('a' + i);
            dfs( trie[node].next[i] );
            rest.pop_back();
        }
    }
}

void solve( const string & p ) {
    int node = 0;
    for(int i = 0; i < p.size(); i++) {
        int letter = (p[i] - 'a');
        if (trie[node].next[letter] == 0) {
            cout << "No match.\n";
            return;
        } else node = trie[node].next[letter];
    }
    rest.clear();
    dfs( node );
}

int main() {
    ios::sync_with_stdio(0);
    int n; cin >> n; cin.ignore(1);
    for(int i = 1; i <= n; i++) {
        string word; getline(cin, word);
        insert(word);
    }
    int q; cin >> q; cin.ignore(1);
    for(int i = 1; i <= q; i++) {
        getline(cin, p);
        cout << "Case #" << i << ":\n";
        solve( p );
    }
    
    return 0;
}

Độ phức tạp:
– Nếu có N words và độ dài mỗi word trung bình M thì Trie của N words này được xây dựng trong O(NM)
– Để xử lí một word có độ dài M trên xâu thì thông thường mất O(M)

Ghi chú:
– Thuật toán xây dựng Trie đơn giản, dễ nhớ, dễ hiểu
– Nếu có N words và độ dài mỗi word trung bình M thì Trie sẽ có tối đa N*M node
– Tuỳ vào bài toán mà chúng ta thêm thông tin cho node của cây Trie. Trong bài tập ở trên, ở mỗi node, chúng ta chỉ cần lưu chỉ số của node tiếp theo tương ứng với từng kí tự (cái này chắc chẳn phải có rồi) và biến w với ý nghĩa: word có được khi duyệt từ node 0 (root) đến node i nếu có trong từ điển thì Trie[i].w = true.

Happy coding,

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s