A suffix trie is a type of trie mainly used for representing all the suffixes of a string. It is a tree where each node represents the suffix of a string. The root node is the entire string, and each child node is a suffix of the string that’s one character shorter than the parent node’s suffix.
For example, consider the string “banana”. The suffix trie for this string would look like this:
root
/ | \
b a n
/ | \
a n a
/ | \
n a n
/ | \
a n a
/ | \
n a $
/ |
a $
/
$
Each path from the root to a leaf node represents a suffix of the string. The leaf nodes represent the end of a suffix, and the dollar sign ($) is used to indicate the end of the string.
The children store entire word instead of characters.
Features of Suffix Tries
Following are the Features of Suffix Tries −
Operations on Suffix Tries
Some of the common operations on suffix tries include:
- Insertion: Insert a new suffix into the trie.
- Deletion: Remove a suffix from the trie.
- Search: Find a specific suffix in the trie.
Insertion Operation on Suffix Tries
We can insert a new suffix into the trie by following these steps:
1. Start at the root node.
2. For each character in the suffix:
a. If the character is not in the current node's children, create a new node for the same.
b. Then move to the child node corresponding to the character and repeat the process.
3. Repeat the process for all character in the suffix.
4. Mark the last node as a leaf node to indicate the end of the suffix.
Code for Insertion Operation
For example, to insert the suffix “ana” into the trie, we would follow these steps:
// C Program to insert a suffix into a trie#include <stdio.h>#include <stdlib.h>#define ALPHABET_SIZE 26// Structure for trie nodestructTrieNode{structTrieNode* children[ALPHABET_SIZE];int isEndOfWord;};// Function to create a new trie nodestructTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
node->isEndOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
node->children[i]=NULL;}return node;}// Function to insert a suffix into the trievoidinsert(structTrieNode* root,constchar* suffix){structTrieNode* current = root;for(int i =0; suffix[i]!='\0'; i++){int index = suffix[i]-'a';if(current->children[index]==NULL){
current->children[index]=createNode();}
current = current->children[index];}
current->isEndOfWord =1;}// Display the trievoiddisplay(structTrieNode* root,char str[],int level){if(root->isEndOfWord){
str[level]='\0';printf("%s\n", str);}for(int i =0; i < ALPHABET_SIZE; i++){if(root->children[i]!=NULL){
str[level]= i +'a';display(root->children[i], str, level +1);}}}intmain(){structTrieNode* root =createNode();insert(root,"banana");insert(root,"ana");insert(root,"na");insert(root,"a");insert(root,"$");char str[20];// Allocating memory for string bufferdisplay(root, str,0);return0;}
Output
Following is the output of the above code:
a ana banana na
Deletion and Search Operations on Suffix Tries
Deletion and search operations on suffix tries are similar to insertion. We can delete a suffix by removing the corresponding leaf node from the trie. To search for a specific suffix, we can traverse the trie from the root node to the leaf node corresponding to the suffix.
Following are the steps to delete a suffix from the trie:
1. Start at the root node.
2. For each character in the suffix:
a. Move to the child node corresponding to the character.
3. Mark the last node as a non-leaf node to delete the suffix.
Following are the steps to search for a specific suffix in the trie:
1. Start at the root node.
2. For each character in the suffix:
a. Move to the child node corresponding to the character.
3. Check if the last node is a leaf node to find the suffix.
Code for Deletion and Search Operations
Here is the code for deletion and search operations on suffix tries:
// C Program to delete and search a suffix in a trie#include <stdio.h>#include <stdlib.h>#define ALPHABET_SIZE 26// Structure for trie nodestructTrieNode{structTrieNode* children[ALPHABET_SIZE];int isEndOfWord;};// Function to create a new trie nodestructTrieNode*createNode(){structTrieNode* node =(structTrieNode*)malloc(sizeof(structTrieNode));
node->isEndOfWord =0;for(int i =0; i < ALPHABET_SIZE; i++){
node->children[i]=NULL;}return node;}// Function to insert a suffix into the trievoidinsert(structTrieNode* root,constchar* suffix){structTrieNode* current = root;for(int i =0; suffix[i]!='\0'; i++){int index = suffix[i]-'a';if(current->children[index]==NULL){
current->children[index]=createNode();}
current = current->children[index];}
current->isEndOfWord =1;}// Function to delete a suffix from the trievoiddelete(structTrieNode* root,constchar* suffix){structTrieNode* current = root;for(int i =0; suffix[i]!='\0'; i++){int index = suffix[i]-'a';if(current->children[index]==NULL){return;// Suffix not found}
current = current->children[index];}
current->isEndOfWord =0;}// Function to search for a suffix in the trieintsearch(structTrieNode* root,constchar* suffix){structTrieNode* current = root;for(int i =0; suffix[i]!='\0'; i++){int index = suffix[i]-'a';if(current->children[index]==NULL){return0;// Suffix not found}
current = current->children[index];}return current->isEndOfWord;}intmain(){structTrieNode* root =createNode();insert(root,"banana");insert(root,"ana");insert(root,"na");insert(root,"a");insert(root,"$");printf("Search for 'ana': %s\n",search(root,"ana")?"Found":"Not found");delete(root,"ana");printf("After deletion:\n");printf("Search for 'ana': %s\n",search(root,"ana")?"Found":"Not found");printf("Search for 'na': %s\n",search(root,"na")?"Found":"Not found");return0;}
Output
Following is the output of the above code:
Search for 'ana': Found After deletion: Search for 'ana': Not found Search for 'na': Found
Time Complexity of Suffix Tries
The time complexity of suffix tries depends on the operations performed:
- Insertion: O(n) for inserting a suffix of length n into the trie.
- Deletion: O(n)
- Search: O(n)
Applications of Suffix Tries
Suffix tries are used in various applications, including:
- Pattern matching and substring search algorithms
- Text indexing and searching
- Genomic sequence analysis
- Spell checking and correction
- Biological sequence analysis
- Information retrieval
- Compression algorithms
Conclusion
In this chapter, we discussed suffix tries, a type of trie used for representing all the suffixes of a string. We explored the structure of a suffix trie, its features, operations, and applications. Suffix tries are a powerful data structure for substring searches, pattern matching, and other string-related operations.
