Блог пользователя AksLolCoding

How Not to Code a Trie
Автор AksLolCoding, 3 часа назад, По-английски

Below is a snippet from a trie implementation (the trie is stored in the 1-indexed vector t):

int get(int &u) {
    if (!u) {
        t.emplace_back();
        u = size(t)-1;
    }
    return u;
}
int insert(string s) {
    int u = 1;
    for (char c : s) {
        u = get(t[u].child[c-'a']);
    }
    return u;
}

This code is incorrect; can you figure out why?

Answer
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
3 часа назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится

A simple fix is to avoid passing a reference into t across emplace_back(). For example, make get take the child index by value and return the new index:

int get(int u) {
    if (!u) {
        t.emplace_back();
        u = t.size() - 1;
    }
    return u;
}

Then the original u = get(t[u].child[c - 'a']); is safe.

→ Ответить
  • »
    »
    3 часа назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    This is also wrong: it doesn't update t[u].child[c-'a'] when a node is created

    → Ответить
    • »
      »
      »
      3 часа назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      How about changing get to take the parent/index instead of the child reference

      int get(int u, int c) {
    if (!t[u].child[c]) {
        t.emplace_back();
        t[u].child[c] = t.size() - 1;
    }
    return t[u].child[c];
}

      Then:

      u = get(u, c - 'a');

      This keeps the write-back behavior, while no reference into t survives the emplace_back().

      → Ответить