代码 1:t[u][c] = newNode();,测样例时,在 Windows 中输出错误答案,在 Linux 中开启 Address Sanitizer 后测试出现 heap-use-after-free 错误。
代码 2:int s = nowNode(); t[u][c] = s; 正确。
这两份代码究竟有什么区别??
我的代码用了 vector,没有在一开始就给所有节点分配内存池,而是在需要新建节点时,才在 newNode() 中扩容:
struct Trie
{
vector<array<int, Sig>> t;
vector<int> vis;
int tot;
int newNode()
{
array<int, Sig> tmp;
tmp.fill(0);
t.push_back(tmp), vis.push_back(0); // 动态扩容
return tot++;
}
Trie() { tot = 0, newNode(); }
void insert(string &str)
{
int u = 0;
for(char ch: str)
{
int c = ch - 'a';
if(!t[u][c])
{
// int s = newNode();
t[u][c] = newNode();
}
u = t[u][c];
}
vis[u] = 1;
}
};
错误会不会和这有关?因为我发现,如果把 vector 改成 array,在一开始分配好内存池而不是在 newNode() 中扩容,代码 1 就对了。但我不知道原因是什么。
完整错误代码