字典树(Trie)【非动态申请内存实现】

字典树(Trie)【非动态申请内存实现】

程序竞赛中常常会用到字典树,我们知道,通常的竞赛中数据量是给定大小的,那么我们便不必要动态申请内存去创建字典树,我们完全可以通过预先开数组的方法来实现这棵字典树,以避免new或者malloc的时间消耗。

数组实现版:

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

const int SIZE_OF_ALPHABET = 26;
const int LIM = 200;
const int NIL = -1;
struct Node {
    int idx[SIZE_OF_ALPHABET];
    bool isEndOfWord;
} trie[LIM];
int len = 0;

void init() {
    len = 0;
    for (int i = 0; i < LIM; i++) {
        memset(trie[i].idx, NIL ,sizeof(trie[i].idx));
        trie[i].isEndOfWord = false;
    }
}

void insert(const string &str) {
    int crt = 0;
    for (int i = 0; i < str.size(); i++) {
        int key = str[i] - 'a';
        if (trie[crt].idx[key] == NIL) trie[crt].idx[key] = ++len;
        crt = trie[crt].idx[key];
    }
    trie[crt].isEndOfWord = true;
}

bool query(const string &str) {
    int crt = 0;
    for (int i = 0; i < str.size(); i++) {
        int key = str[i] - 'a';
        if (trie[crt].idx[key] == NIL) return false;
        crt = trie[crt].idx[key];
    }
    return trie[crt].isEndOfWord;
}

int main(void) {
    init();
    /* Do something here */
    return 0;
}

 

vector+map实现:

#include <iostream>
#include <map>
#include <vector>
#include <string>

using namespace std;

struct Node {
    map<char, int> idx;
    bool EOW;           // the end of word
    Node() : EOW(false) {}
};
vector<Node> trie;

inline void init() {
    trie.clear();
    // create the head node
    trie.push_back(Node());
}

void insert(const string &str) {
    int crt = 0;
    for (int i = 0; i < str.size(); i++) {
        if (!trie[crt].idx[str[i]]) {
            trie[crt].idx[str[i]] = trie.size();
            trie.push_back(Node());
        }
        crt = trie[crt].idx[str[i]];
    }
    trie[crt].EOW = true;
}

bool query(const string &str) {
    int crt = 0;
    for (int i = 0; i < str.size(); i++) {
        if (!trie[crt].idx[str[i]]) return false;
        crt = trie[crt].idx[str[i]];
    }
    return trie[crt].EOW;
}

int main(void) {
    init();
    /* Do something here */
    return 0;
}