Hello, ↵
↵
I was implementing a simple Trie when I found a behavior that I didn't understand. I followed the program using a debugger. I commented in the code above the part where the issue seems to be, the issue seems to be in the `insert` function. I explained the issue in code comments.↵
↵
~~~~~↵
struct Trie{↵
struct Node{↵
int id, nxt[26];↵
Node(int id) : id(id)↵
{↵
memset(nxt, -1, sizeof(nxt));↵
}↵
};↵
vector<Node> v;↵
vector<bool> leaf;↵
void init()↵
{↵
v.clear();↵
leaf.clear();↵
addNode();↵
}↵
↵
int addNode()↵
{↵
v.push_back(v.size());↵
leaf.push_back(false);↵
return (int)(v.size()) - 1;↵
}↵
↵
int getSizeMinusOne()↵
{↵
return (int)(v.size()) - 1;↵
}↵
↵
void insert(const string &s)↵
{↵
int cur = 0;↵
for (char c : s)↵
{↵
c -= 'a';↵
if (v[cur].nxt[c] == -1)↵
{↵
// Note I only use one of the following NOT both at the same time↵
↵
// Approach (1)↵
// v[cur].nxt[c] doesn't get updated. Stays -1 and RTEs later on due to out of boundary access↵
v[cur].nxt[c] = addNode();↵
↵
// Approach (2)↵
// works fine↵
addNode();↵
v[cur].nxt[c] = getSizeMinusOne();↵
}↵
cur = v[cur].nxt[c];↵
}↵
leaf[cur] = true;↵
}↵
};↵
~~~~~ ↵
↵
I also found out that both approaches seem to work find when changing the array `nxt` to a vector instead of an array. Could someone explain why this happens when `nxt` is an array? And why approach (2) works fine even if `nxt` is an array?
↵
I was implementing a simple Trie when I found a behavior that I didn't understand. I followed the program using a debugger
↵
~~~~~↵
struct Trie{↵
struct Node{↵
int id, nxt[26];↵
Node(int id) : id(id)↵
{↵
memset(nxt, -1, sizeof(nxt));↵
}↵
};↵
vector<Node> v;↵
vector<bool> leaf;↵
void init()↵
{↵
v.clear();↵
leaf.clear();↵
addNode();↵
}↵
↵
int addNode()↵
{↵
v.push_back(v.size());↵
leaf.push_back(false);↵
return (int)(v.size()) - 1;↵
}↵
↵
int getSizeMinusOne()↵
{↵
return (int)(v.size()) - 1;↵
}↵
↵
void insert(const string &s)↵
{↵
int cur = 0;↵
for (char c : s)↵
{↵
c -= 'a';↵
if (v[cur].nxt[c] == -1)↵
{↵
// Note I only use one of the following NOT both at the same time↵
↵
// Approach (1)↵
// v[cur].nxt[c] doesn't get updated. Stays -1 and RTEs later on due to out of boundary access↵
v[cur].nxt[c] = addNode();↵
↵
// Approach (2)↵
// works fine↵
addNode();↵
v[cur].nxt[c] = getSizeMinusOne();↵
}↵
cur = v[cur].nxt[c];↵
}↵
leaf[cur] = true;↵
}↵
};↵
~~~~~ ↵
↵
I also found out that both approaches seem to work find when changing the array `nxt` to a vector instead of an array. Could someone explain why this happens when `nxt` is an array? And why approach (2) works fine even if `nxt` is an array?
