AlgoWiki

Trie

A trie is a data structure that allows quick searches in a dictionary. Concretely, searching for a word of length $n$ in a trie has a complexity of $O(n)$, and building a trie has a complexity of $O(L)$, where $L$ is the total length of the words in the dictionary.

A trie is a tree rooted at an empty node, and in which each way from the root to a leaf represents a word in the dictionary. In order to accomplish this task, a node at depth $k$ represents a substring of length $k$, that is the substring represented by the direct ancestor of the current node plus an additional character. Of course, the root represents the empty string. If a certain node represents a whole word in the dictionary, an additional flag should be used to mark this fact.

Applications

Tries can be used to compute longest common prefix, longest common suffix, [longest common substring](Longest common substring), string matching, and string matching with mistakes, to name a few applications.

By augmenting tries, it can be made into a very flexible data structure. See problem Xor Queries for an example.

Variants

When all suffixes of a string are inserted into a trie, the trie is called a suffix trie. This has time and memory complexity $O(n^2)$, where $n$ is the length of the string. [Suffix trees](Suffix tree) achieve this in $O(n)$ time and memory by not explicitly storing all nodes of the trie.

Implementation in C++

class Trie{
    struct node{
        node *next[26];   // Assuming alphabet 'a'-'z'
        bool end;

        node(){
            for(int i=0;i<26;i++)next[i]=this;
            end=0;
        }
    };

    node *begin;

public:

    Trie(){
        begin=new node();
    }

    void insert(const string &s){
        int n=s.length();
        node *cur=begin;

        for(int i=0;i<n;i++){
            if(cur->next[s[i]-'a']!=cur)
                cur=cur->next[s[i]-'a'];
            else{
                node *aux=new node();
                cur->next[s[i]-'a']=aux;
                cur=aux;
            }
        }

        cur->end=true;
    }


    bool find(string &s){    // returns true if s is in the input dictionary.
        int n=s.length();
        node *cur=begin;

        for(int i=0;i<n;i++){
            if(cur->next[s[i]-'a']!=cur)
                cur=cur->next[s[i]-'a'];
            else return false;
        }

        return cur->end;
    }
};

Problems

External links