How to represent a trie in a 2D array?

Revision en1, by maximaxi, 2017-02-11 02:01:19

I have seen some people's code to represent a trie in a 2D array. For example, this is my old code to solve Autocomplete. However, I forgot how it works!

Can someone explain how to code a 2D array that represents a trie? I know that one dimension of the array represents the alphabet, and that the values inside the trie array are the node numbers, where the first letter you add is node number 1. Still, I'm confused where to insert values into the trie array, and how strings with the same prefixes would be distinguished in the tire.

Thanks.

#include <bits/stdc++.h>
#define rd(s) freopen(s, "r", stdin);
#define wt(s) freopen(s, "w", stdout);
using namespace std;

const int MAX=1e6+2, ALF=26+2;
int t, trie[MAX][ALF];

int main()
{
    //rd("test.txt");

    scanf("%d", &t);
    for (int i=1; i<=t; ++i) {
        int ans=0, n, numm1=1;
        for (int _=0; _<MAX; ++_) for (int __=0; __<ALF; ++__) trie[_][__] = 0;
        scanf("%d", &n);
        for (int j=0; j<n; ++j) {
            int node=0, idx=0;
            string word; cin>>word;
            while (trie[node][word[idx]-'a'] && idx < word.length()) {
                node=trie[node][word[idx]-'a'];
                ++ans; ++idx;
            }
            if (idx != word.length()) ++ans;
            //printf("ans is %d\n", ans);
            for (; idx<word.length(); ++idx) {
                trie[node][word[idx]-'a'] = numm1;
                //printf("new path from %d to %d via %c\n", node, numm1, word[idx]);
                node=numm1;
                ++numm1;
            }
        }
        printf("Case #%d: %d\n", i, ans);
    }
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English maximaxi 2017-02-11 02:01:19 1749 Initial revision (published)