# Trie Implementation

## Trie Implementation  in C++

Trie also called suffix trees are important advanced data structures that allows us to search strings in time efficient manner. They are also very efficient to store strings in terms of memory. Tries have many cool applications like auto complete feature in cell phones, searching text, pattern matching etc. Below is a Trie Implementation in C++. ## Why we need Trie?

We will understand implementation of trie using a problem. Suppose we have to make q queries on a text of length n. In each query we are given a string (pattern) of length m and we need to find whether the given string exists in the text or not.

The basic or naive approach to above problem is to try to match the pattern at each character in the text. The worst case time complexity of matching a string will be O(m*n). For q queries the time complexity will be O(q*n*m).

Tries allow us to perform above operation in O(m) for a single string. Therefore the total time complexity for q queries will be O(q*m).

## Trie Implementation in C++ ### Trie Implementation in C++ Algorithm (Insertion):

• Create a class or a structure for the trie node that can point to child nodes. Here we will be using a hash map for marking child nodes.
• Add all suffixes of the given text into trie one by one.
• While adding a suffix to the trie we will check if current node already has a child node for the current character. If node already present we simple move to the child node other wise if node present we create a corresponding node for that character and then move to that newly created node. Repeat this procedure still we reach the end of the suffix.
• Repeat the above procedure for all suffixes.

### Trie Implementation in C++ Algorithm (Searching):

• The algorithm for searching is similar to the insertion algorithm. We start from the head node and first character of the pattern.
• If we have a child node for the current character we move to that node and check for next character.
• Otherwise if we don’t have a node we just return false as this means our pattern is not present in the text.

### C++ Code:

#include <bits/stdc++.h>
using namespace std;
class TrieNode
{
public:
unordered_map<charTrieNode *> M;
};
{
for (int i = 0i < s.length(); i++)
{
char c = s[i];
if (temp->M.find(c== temp->M.end())
temp->M[c] = new TrieNode();

// Move to next node
temp = temp->M[c];
}
}
{
for (int i = 0i < pattern.length(); i++)
{
char c = pattern[i];
// If node for the charactor is not present this means the pattern is note present in the text
if (temp->M.find(c== temp->M.end())
return false;
temp = temp->M[c];
}

return true;
}
int main()
{
string s = “prepinsta”;
string pattern = “repin”pattern2 = “repinx”;
string suffix;
for (int i = s.length() – 1i >= 0i–)
{
suffix = s[i] + suffix;
`Inserting Suffix a in the trieInserting Suffix ta in the trieInserting Suffix sta in the trieInserting Suffix nsta in the trieInserting Suffix insta in the trieInserting Suffix pinsta in the trieInserting Suffix epinsta in the trieInserting Suffix repinsta in the trieInserting Suffix prepinsta in the trieFound repinNot Found repinx`