我今天正在解决一个问题。但我被困住了。我知道特里树是如何工作的,但问题是我知道如何用静态数组和类来实现它。今天在网上冲浪时我读到有一种方法可以使用 stl::map 来实现 attempts。我今天尝试了,但我仍然不知道如何在 int 上插入元素。
这种结构。
Edit1:我正在尝试解决这个问题:spoj.com/problems/TAP2012D
我想知道如何将单词添加到特里树中
edit2:我知道地图是如何工作的,我只是不知道带有地图的特里树如何工作。我想要一个了解尝试的人。
这是我到目前为止所做的
const int ALPH_SIZE = 26;
using namespace std;
struct trie{
map<char,int> M;
int x,y;
trie();
};
trie T[1000000];
trie::trie()
{
x=y=0;
}
int maximo;
void addtrie(string palabra)
{
int tam=palabra.size();
int pos=0;
for(int i=0;i<tam;i++)
{
if(T[pos].M.find(palabra[i])==T[pos].M.end())
{
T[pos].M[palabra[i]]=new trie();
T[pos].M[palabra[i]]=
}
}
}
trie 节点存储现有输出字符的映射和指示该节点是否对应于 trie 中的单词的标志。
struct Node
{ map<char, Node*> a;
bool flag;
Node() { flag = false; }
};
现在,插入与使用静态数组执行的操作类似,只不过这里使用的是映射。
void insert(Node *x, string s)
{ for(int i = 0; i < s.size(); i++)
{ if(x->a.count(s[i]) == 0)
/* no outgoing edge with label = s[i] so make one */
{ x->a[ s[i] ] = new Node;
}
x = x->a[ s[i] ];
}
x->flag = true; /* new word */
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)