使用静态数组的nxt指针的设计,大概比使用map作为nxt指针的设计要快1倍,但空间花费大概也大1倍。在数据量小的情况下,时间和空间效率都不及map<vector
时间复杂度:
初始化:O(sigma)
插入:O(len*sigma)
查询:O(len)
空间复杂度:
O(n*len*sigma)
struct TrieNode {
int data;
int nxt[26];
void init() {
data = 0;
memset(nxt, 0, sizeof(nxt));
}
};
struct Trie {
TrieNode tn[200005];
int root, top;
int newnode() {
tn[++top].init();
return top;
}
void init() {
top = 0;
root = newnode();
}
void insert(int *a, int len, int data) {
int cur = root;
for(int i = 1; i <= len; ++i) {
int &nxt = tn[cur].nxt[a[i] - 'a'];
if(!nxt)
nxt = newnode();
cur = nxt;
}
tn[cur].data = data;
}
int query(int *a, int len) {
int cur = root;
for(int i = 1; i <= len; ++i) {
int &nxt = tn[cur].nxt[a[i] - 'a'];
if(!nxt)
return -1;
cur = nxt;
}
return tn[cur].data;
}
} trie;
原文:https://www.cnblogs.com/KisekiPurin2019/p/11858431.html