使用静态数组的nxt指针的设计,大概比使用map作为nxt指针的设计要快1倍,但空间花费大概也大1倍。在数据量小的情况下,时间和空间效率都不及map<vector
**1. 注意修改Query的实现,默认找不到结果是返回0,就算找到也未必代表字符串在里面出现过,也可能是字符串的其中一个前缀。 **
**2. 注意我写的字符串都是从1开始的,所以传进来的字符串指针不需要+1。 **
**3. 注意MAXN并不是最大的句子的个数,而是最大的节点的个数,也就是 (MAXN=n*len)。 **
时间复杂度:
初始化: (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 {
static const int MAXN = 200000;
TrieNode tn[MAXN + 5];
int root, top;
int NewNode() {
tn[++top].Init();
return top;
}
void Init() {
top = 0;
root = NewNode();
}
void Insert(char *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(char *a, int len) {
int cur = root;
for(int i = 1; i <= len; ++i) {
int &nxt = tn[cur].nxt[a[i] - 'a'];
if(!nxt)
return 0;
cur = nxt;
}
return tn[cur].data;
}
} trie;