# 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;   // 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;
}
};