首页 > 代码库 > 【Trie】Trie字典树模板 静态指针池、数组写法
【Trie】Trie字典树模板 静态指针池、数组写法
下面是数组写法：
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define idx(x) x - 'a';
const int MAXN = 1e6;
struct Trie {
int next[26];
int val;
}tree[MAXN];
int nxt, T;
char str[MAXN];
int add()
{
memset(&tree[nxt], 0, sizeof(Trie));
return nxt++;
}
void Insert(char *s)
{
int rt = 0, len = strlen(s);
for(int i = 0; i < len; i++) {
int c = idx(s[i]);
if(!tree[rt].next[c]) {
tree[rt].next[c] = add();
}
rt = tree[rt].next[c];
}
tree[rt].val++;
}
bool Find(char *s)
{
int rt = 0, len = strlen(s);
for(int i = 0; i < len; i++) {
int c = idx(s[i]);
if(!tree[rt].next[c])
return false;
rt = tree[rt].next[c];
}
if(tree[rt].val) return true;
return false;
}
int main()
{
memset(&tree[0], 0, sizeof(Trie));
nxt = 1;
scanf("%d", &T);
while(T--) {
scanf("%s", str);
Insert(str);
}
while(~scanf("%s", str)) {
if(Find(str)) puts("exist");
else puts("none");
}
return 0;
}下面是静态指针池写法：
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define idx(x) x - 'a';
const int MAXN = 1e6;
struct Trie {
Trie *next[26];
int val;
}tree[MAXN];
int nxt, T;
char str[MAXN];
Trie *add()
{
memset(&tree[nxt], 0, sizeof(Trie));
return &tree[nxt++];
}
void Insert(Trie *rt, char *s)
{
int len = strlen(s);
for(int i = 0; i < len; i++) {
int c = idx(s[i]);
if(!rt->next[c])
rt->next[c] = add();
rt = rt->next[c];
}
rt->val++;
}
bool Find(Trie *rt, char *s)
{
int len = strlen(s);
for(int i = 0; i < len; i++) {
int c = idx(s[i]);
if(!rt->next[c])
return false;
rt = rt->next[c];
}
if(rt->val) return true;
return false;
}
int main()
{
nxt = 0;
Trie *root = add();
scanf("%d", &T);
while(T--) {
scanf("%s", str);
Insert(root, str);
}
while(~scanf("%s", str)) {
if(Find(root, str)) puts("exist");
else puts("none");
}
return 0;
}【Trie】Trie字典树模板 静态指针池、数组写法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。