Pattern Searching in Trie tree
In this article, we'll explore the concept of pattern searching in a Trie tree. A Trie, also known as a prefix tree, is a data structure used for efficient string storage and retrieval. Pattern searching involves finding specific patterns (substrings) within a given text using a Trie tree. We will walk through the problem statement, present a step-by-step solution, provide pseudocode, algorithm explanation, an example, output interpretation, and conclude with the time complexity analysis.
Problem Statement
Given a dictionary of words, construct a Trie tree with those words. Then, find occurrences of any dictionary word as a substring in a given text and identify the starting position of each occurrence.
Example Scenario
Let's consider a dictionary of words: "go," "to," "tool," "old," "gold," "code," "his," "co," and "good." Our text is "wintooldgoldcogood." We want to find occurrences of dictionary words within this text.
Idea to Solve
- Construct a Trie using the dictionary words.
- For each character in the given text, check if the current character matches the starting character of any dictionary word in the Trie.
- If a match is found, traverse the Trie to check for the presence of the remaining characters of the dictionary word.
- If the entire dictionary word is found in the Trie, print its occurrence.
Pseudocode
class Node:
boolean stop
Node[26] children
class Trie:
Node root
insert(word):
node = root
for char in word:
index = char - 'a'
if node.children[index] is None:
node.children[index] = new Node()
node = node.children[index]
node.stop = true
search_pattern(head, text, start, i, size, result):
if head is not None and i < size and head.children[text[i] - 'a'] is not None:
node = head.children[text[i] - 'a']
ans = result + text[i]
if node.stop:
print("Word [" + ans + "] appears from " + start + "," + i)
search_pattern(node, text, start, i + 1, size, ans)
find_pattern(text):
size = length(text)
if root is None or size <= 0:
return
print("Given String: " + text)
print("Search Word: ")
for i in 0 to size - 1:
if root.children[text[i] - 'a'] is not None:
search_pattern(root, text, i, i, size, "")
Algorithm Explanation
- Create a Trie object and insert dictionary words into the Trie using the
insert
function. - For each character in the given text, if the Trie contains the corresponding character, call the
search_pattern
function. - Within
search_pattern
, traverse the Trie while matching characters in the text. - If a valid word (stop) is found in the Trie, print its occurrence and starting position.
- In the
find_pattern
function, iterate through the text to find potential starting characters of dictionary words.
Code Solution
// Java program
// Pattern Searching in Trie tree
class Node
{
//Indicates end of string
public boolean stop;
public Node[] children;
public Node()
{
this.stop = false;
this.children = new Node[26];
}
}
public class Trie
{
public Node root;
public Trie()
{
this.root = new Node();
}
// This function are handles the request to add element in tire
public void insert(String text)
{
//First get the length of text
int length = text.length();
//This variable are used to task find the index location of character
int index = 0;
//Get the root node
Node head = this.root;
for (int level = 0; level < length; level++)
{
//Get the index
index = text.charAt(level) - 'a';
if (head.children[index] == null)
{
//When need to add new Node
head.children[index] = new Node();
}
head = head.children[index];
}
if (head != null)
{
//Indicates end of string
head.stop = true;
}
}
// This is display the elements of trie tree
public void display(Node head, String about)
{
if (head != null)
{
if (head.stop == true)
{
System.out.println(about);
}
for (int i = 0; i < 26; i++)
{
if (head.children[i] != null)
{
display(head.children[i], about + ((char)(i + 'a')));
}
}
}
}
//Pattern Searching
public void search_pattern(Node head, String text, int start, int i, int size, String result)
{
if (head != null && i < size && head.children[text.charAt(i) - 'a'] != null)
{
Node node = head.children[text.charAt(i) - 'a'];
String ans = result + text.charAt(i);
if (node.stop == true)
{
// When tire words are completing
System.out.print("\n Word [" + ans + "] appears from " + start + "," + i);
}
search_pattern(node, text, start, i + 1, size, ans);
}
}
// Handles the request of finding given text pattern in trie tree
public void find_pattern(String text)
{
int size = text.length();
if (this.root == null || size <= 0)
{
return;
}
System.out.print("\n Given String : "+text);
System.out.print("\n Search Word ");
for (int i = 0; i < size; i++)
{
// Check whether root of trie tree contain text character
if (this.root.children[text.charAt(i) - 'a'] != null)
{
search_pattern(this.root, text, i, i, size, "");
}
}
}
public static void main(String args[])
{
Trie obj = new Trie();
String[] dictionary = {
"go" , "to" , "tool" , "old" ,"gold" , "code" , "his" , "co" , "good"
};
int size = dictionary.length;
//Add dictionary element
for (int i = 0; i < size; i++)
{
obj.insert(dictionary[i]);
}
System.out.print("\nTrie Element\n");
obj.display(obj.root, "");
String text = "wintooldgoldcogood";
obj.find_pattern(text);
}
}
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [to] appears from 3,4
Word [tool] appears from 3,6
Word [old] appears from 5,7
Word [go] appears from 8,9
Word [gold] appears from 8,11
Word [old] appears from 9,11
Word [co] appears from 12,13
Word [go] appears from 14,15
Word [good] appears from 14,17
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Pattern Searching in Trie tree
*/
//This is tire tree node
class Node
{
public:
//Indicates stop of string
bool stop;
Node *children[26];
Node()
{
this->stop = false;
for (int i = 0; i < 26; ++i)
{
this->children[i] = NULL;
}
}
};
class Trie
{
public: Node *root;
Trie()
{
this->root = new Node();
}
// This function are handles the request to add element in tire
void insert(string text)
{
// First get the length of text
int length = text.length();
// This variable are used to task find the index location of character
int index = 0;
// Get the root node
Node *head = this->root;
for (int level = 0; level < length; level++)
{
// Get the index
index = text[level] - 'a';
if (head->children[index] == NULL)
{
// When need to add new Node
head->children[index] = new Node();
}
head = head->children[index];
}
if (head != NULL)
{
// Indicates end of string
head->stop = true;
}
}
// This is display the elements of trie tree
void display(Node *head, string about)
{
if (head != NULL)
{
if (head->stop == true)
{
cout << about << endl;
}
for (int i = 0; i < 26; i++)
{
if (head->children[i] != NULL)
{
this->display(head->children[i], about + ((char)(i + 'a')));
}
}
}
}
// Pattern Searching
void search_pattern(Node *head, string text, int start, int i, int size, string result)
{
if (head != NULL && i < size && head->children[text[i] - 'a'] != NULL)
{
Node *node = head->children[text[i] - 'a'];
string ans = result + text[i];
if (node->stop == true)
{
// When tire words are completing
cout << "\n Word [" << ans << "] appears from " << start << "," << i;
}
this->search_pattern(node, text, start, i + 1, size, ans);
}
}
// Handles the request of finding given text pattern in trie tree
void find_pattern(string text)
{
int size = text.length();
if (this->root == NULL || size <= 0)
{
return;
}
cout << "\n Given String : " << text;
cout << "\n Search Word ";
for (int i = 0; i < size; i++)
{
// Check whether root of trie tree contain text character
if (this->root->children[text[i] - 'a'] != NULL)
{
this->search_pattern(this->root, text, i, i, size, "");
}
}
}
};
int main()
{
Trie obj = Trie();
string dictionary[] = {
"go" , "to" , "tool" , "old" , "gold" , "code" , "his" , "co" , "good"
};
int size = sizeof(dictionary) / sizeof(dictionary[0]);
// Add dictionary element
for (int i = 0; i < size; i++)
{
obj.insert(dictionary[i]);
}
cout << "\nTrie Element\n";
obj.display(obj.root, "");
string text = "wintooldgoldcogood";
obj.find_pattern(text);
return 0;
}
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [to] appears from 3,4
Word [tool] appears from 3,6
Word [old] appears from 5,7
Word [go] appears from 8,9
Word [gold] appears from 8,11
Word [old] appears from 9,11
Word [co] appears from 12,13
Word [go] appears from 14,15
Word [good] appears from 14,17
// Include namespace system
using System;
// C# program
// Pattern Searching in Trie tree
public class Node
{
// Indicates end of string
public Boolean stop;
public Node[] children;
public Node()
{
this.stop = false;
this.children = new Node[26];
}
}
public class Trie
{
public Node root;
public Trie()
{
this.root = new Node();
}
// This function are handles the request to add element in tire
public void insert(String text)
{
// First get the length of text
int length = text.Length;
// This variable are used to task find the index location of character
int index = 0;
// Get the root node
Node head = this.root;
for (int level = 0; level < length; level++)
{
// Get the index
index = text[level] - 'a';
if (head.children[index] == null)
{
// When need to add new Node
head.children[index] = new Node();
}
head = head.children[index];
}
if (head != null)
{
// Indicates end of string
head.stop = true;
}
}
// This is display the elements of trie tree
public void display(Node head, String about)
{
if (head != null)
{
if (head.stop == true)
{
Console.Write("\n" + about);
}
for (int i = 0; i < 26; i++)
{
if (head.children[i] != null)
{
display(head.children[i], about + ((char)(i + 'a')));
}
}
}
}
// Pattern Searching
public void search_pattern(Node head, String text, int start, int i, int size, String result)
{
if (head != null && i < size && head.children[text[i] - 'a'] != null)
{
Node node = head.children[text[i] - 'a'];
String ans = result + text[i];
if (node.stop == true)
{
// When tire words are completing
Console.Write("\n Word [" + ans + "] appears from " + start + "," + i);
}
search_pattern(node, text, start, i + 1, size, ans);
}
}
// Handles the request of finding given text pattern in trie tree
public void find_pattern(String text)
{
int size = text.Length;
if (this.root == null || size <= 0)
{
return;
}
Console.Write("\n\n Given String : " + text);
Console.Write("\n Search Word ");
for (int i = 0; i < size; i++)
{
// Check whether root of trie tree contain text character
if (this.root.children[text[i] - 'a'] != null)
{
search_pattern(this.root, text, i, i, size, "");
}
}
}
public static void Main(String[] args)
{
Trie obj = new Trie();
String[] dictionary = {
"go" , "to" , "tool" , "old" , "gold" , "code" , "his" , "co" , "good"
};
int size = dictionary.Length;
// Add dictionary element
for (int i = 0; i < size; i++)
{
obj.insert(dictionary[i]);
}
Console.Write("\nTrie Element\n");
obj.display(obj.root, "");
String text = "wintooldgoldcogood";
obj.find_pattern(text);
}
}
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [to] appears from 3,4
Word [tool] appears from 3,6
Word [old] appears from 5,7
Word [go] appears from 8,9
Word [gold] appears from 8,11
Word [old] appears from 9,11
Word [co] appears from 12,13
Word [go] appears from 14,15
Word [good] appears from 14,17
<?php
// Php program
// Pattern Searching in Trie tree
class Node
{
// Indicates end of string
public $stop;
public $children;
function __construct()
{
$this->stop = false;
$this->children = array_fill(0, 26, null);
}
}
class Trie
{
public $root;
function __construct()
{
$this->root = new Node();
}
// This function are handles the request to add element in tire
public function insert($text)
{
// First get the length of text
$length = strlen($text);
// This variable are used to task find the index location of character
$index = 0;
// Get the root node
$head = $this->root;
for ($level = 0; $level < $length; $level++)
{
// Get the index
$index = ord($text[$level]) - ord('a');
if ($head->children[$index] == null)
{
// When need to add new Node
$head->children[$index] = new Node();
}
$head = $head->children[$index];
}
if ($head != null)
{
// Indicates end of string
$head->stop = true;
}
}
// This is display the elements of trie tree
public function display($head, $about)
{
if ($head != null)
{
if ($head->stop == true)
{
echo "\n". $about;
}
for ($i = 0; $i < 26; $i++)
{
if ($head->children[$i] != null)
{
$this->display($head->children[$i], $about . (chr($i + ord('a'))));
}
}
}
}
// Pattern Searching
public function search_pattern($head, $text, $start, $i, $size, $result)
{
if ($head != null && $i < $size && $head->children[ord($text[$i]) - ord('a')] != null)
{
$node = $head->children[ord($text[$i]) - ord('a')];
$ans = $result . $text[$i];
if ($node->stop == true)
{
// When tire words are completing
echo "\n Word [". $ans ."] appears from ". $start .",". $i;
}
$this->search_pattern($node, $text, $start, $i + 1, $size, $ans);
}
}
// Handles the request of finding given text pattern in trie tree
public function find_pattern($text)
{
$size = strlen($text);
if ($this->root == null || $size <= 0)
{
return;
}
echo "\n\n Given String : ". $text;
echo "\n Search Word ";
for ($i = 0; $i < $size; $i++)
{
// Check whether root of trie tree contain text character
if ($this->root->children[ord($text[$i]) - ord('a')] != null)
{
$this->search_pattern($this->root, $text, $i, $i, $size, "");
}
}
}
}
function main()
{
$obj = new Trie();
$dictionary = array("go", "to", "tool", "old", "gold", "code", "his", "co", "good");
$size = count($dictionary);
// Add dictionary element
for ($i = 0; $i < $size; $i++)
{
$obj->insert($dictionary[$i]);
}
echo "\nTrie Element\n";
$obj->display($obj->root, "");
$text = "wintooldgoldcogood";
$obj->find_pattern($text);
}
main();
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [to] appears from 3,4
Word [tool] appears from 3,6
Word [old] appears from 5,7
Word [go] appears from 8,9
Word [gold] appears from 8,11
Word [old] appears from 9,11
Word [co] appears from 12,13
Word [go] appears from 14,15
Word [good] appears from 14,17
// Node Js program
// Pattern Searching in Trie tree
class Node
{
// Indicates end of string
constructor()
{
this.stop = false;
this.children = Array(26).fill(null);
}
}
class Trie
{
constructor()
{
this.root = new Node();
}
// This function are handles the request to add element in tire
insert(text)
{
// First get the length of text
var length = text.length;
// This variable are used to task find the index location of character
var index = 0;
// Get the root node
var head = this.root;
for (var level = 0; level < length; level++)
{
// Get the index
index = (text[level]).charCodeAt(0) - ('a').charCodeAt(0);
if (head.children[index] == null)
{
// When need to add new Node
head.children[index] = new Node();
}
head = head.children[index];
}
if (head != null)
{
// Indicates end of string
head.stop = true;
}
}
// This is display the elements of trie tree
display(head, about)
{
if (head != null)
{
if (head.stop == true)
{
process.stdout.write("\n" + about);
}
for (var i = 0; i < 26; i++)
{
if (head.children[i] != null)
{
this.display(head.children[i], about + (String.fromCharCode((i + ('a').charCodeAt(0)))));
}
}
}
}
// Pattern Searching
search_pattern(head, text, start, i, size, result)
{
if (head != null && i < size && head.children[(text[i]).charCodeAt(0) - ('a').charCodeAt(0)] != null)
{
var node = head.children[(text[i]).charCodeAt(0) - ('a').charCodeAt(0)];
var ans = result + text[i];
if (node.stop == true)
{
// When tire words are completing
process.stdout.write("\n Word [" + ans + "] appears from " + start + "," + i);
}
this.search_pattern(node, text, start, i + 1, size, ans);
}
}
// Handles the request of finding given text pattern in trie tree
find_pattern(text)
{
var size = text.length;
if (this.root == null || size <= 0)
{
return;
}
process.stdout.write("\n\n Given String : " + text);
process.stdout.write("\n Search Word ");
for (var i = 0; i < size; i++)
{
// Check whether root of trie tree contain text character
if (this.root.children[(text[i]).charCodeAt(0) - ('a').charCodeAt(0)] != null)
{
this.search_pattern(this.root, text, i, i, size, "");
}
}
}
}
function main()
{
var obj = new Trie();
var dictionary = ["go", "to", "tool", "old", "gold", "code", "his", "co", "good"];
var size = dictionary.length;
// Add dictionary element
for (var i = 0; i < size; i++)
{
obj.insert(dictionary[i]);
}
process.stdout.write("\nTrie Element\n");
obj.display(obj.root, "");
var text = "wintooldgoldcogood";
obj.find_pattern(text);
}
main();
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [to] appears from 3,4
Word [tool] appears from 3,6
Word [old] appears from 5,7
Word [go] appears from 8,9
Word [gold] appears from 8,11
Word [old] appears from 9,11
Word [co] appears from 12,13
Word [go] appears from 14,15
Word [good] appears from 14,17
# Python 3 program
# Pattern Searching in Trie tree
class Node :
# Indicates end of string
def __init__(self) :
self.stop = False
self.children = [None] * (26)
class Trie :
def __init__(self) :
self.root = Node()
# This function are handles the request to add element in tire
def insert(self, text) :
# First get the length of text
length = len(text)
# This variable are used to task find the index location of character
index = 0
# Get the root node
head = self.root
level = 0
while (level < length) :
# Get the index
index = ord(text[level]) - ord('a')
if (head.children[index] == None) :
# When need to add new Node
head.children[index] = Node()
head = head.children[index]
level += 1
if (head != None) :
# Indicates end of string
head.stop = True
# This is display the elements of trie tree
def display(self, head, about) :
if (head != None) :
if (head.stop == True) :
print("\n", about, end = "")
i = 0
while (i < 26) :
if (head.children[i] != None) :
self.display(head.children[i], about + (chr((i + ord('a')))))
i += 1
# Pattern Searching
def search_pattern(self, head, text, start, i, size, result) :
if (head != None and i < size and head.children[ord(text[i]) - ord('a')] != None) :
node = head.children[ord(text[i]) - ord('a')]
ans = result + text[i]
if (node.stop == True) :
# When tire words are completing
print("\n Word [", ans ,"] appears from ", start ,",", i, end = "")
self.search_pattern(node, text, start, i + 1, size, ans)
# Handles the request of finding given text pattern in trie tree
def find_pattern(self, text) :
size = len(text)
if (self.root == None or size <= 0) :
return
print("\n\n Given String : ", text, end = "")
print("\n Search Word ", end = "")
i = 0
while (i < size) :
# Check whether root of trie tree contain text character
if (self.root.children[ord(text[i]) - ord('a')] != None) :
self.search_pattern(self.root, text, i, i, size, "")
i += 1
def main() :
obj = Trie()
dictionary = ["go", "to", "tool", "old", "gold", "code", "his", "co", "good"]
size = len(dictionary)
# Add dictionary element
i = 0
while (i < size) :
obj.insert(dictionary[i])
i += 1
print("\nTrie Element\n", end = "")
obj.display(obj.root, "")
text = "wintooldgoldcogood"
obj.find_pattern(text)
if __name__ == "__main__": main()
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [ to ] appears from 3 , 4
Word [ tool ] appears from 3 , 6
Word [ old ] appears from 5 , 7
Word [ go ] appears from 8 , 9
Word [ gold ] appears from 8 , 11
Word [ old ] appears from 9 , 11
Word [ co ] appears from 12 , 13
Word [ go ] appears from 14 , 15
Word [ good ] appears from 14 , 17
# Ruby program
# Pattern Searching in Trie tree
class Node
# Define the accessor and reader of class Node
attr_reader :stop, :children
attr_accessor :stop, :children
# Indicates end of string
def initialize()
self.stop = false
self.children = Array.new(26) {nil}
end
end
class Trie
# Define the accessor and reader of class Trie
attr_reader :root
attr_accessor :root
def initialize()
self.root = Node.new()
end
# This function are handles the request to add element in tire
def insert(text)
# First get the length of text
length = text.length()
# This variable are used to task find the index location of character
index = 0
# Get the root node
head = self.root
level = 0
while (level < length)
# Get the index
index = (text[level]).ord - ('a').ord
if (head.children[index] == nil)
# When need to add new Node
head.children[index] = Node.new()
end
head = head.children[index]
level += 1
end
if (head != nil)
# Indicates end of string
head.stop = true
end
end
# This is display the elements of trie tree
def display(head, about)
if (head != nil)
if (head.stop == true)
print("\n", about)
end
i = 0
while (i < 26)
if (head.children[i] != nil)
self.display(head.children[i], about + ((i + 97).chr))
end
i += 1
end
end
end
# Pattern Searching
def search_pattern(head, text, start, i, size, result)
if (head != nil && i < size && head.children[(text[i]).ord - ('a').ord] != nil)
node = head.children[(text[i]).ord - ('a').ord]
ans = result + text[i]
if (node.stop == true)
# When tire words are completing
print("\n Word [", ans ,"] appears from ", start ,",", i)
end
self.search_pattern(node, text, start, i + 1, size, ans)
end
end
# Handles the request of finding given text pattern in trie tree
def find_pattern(text)
size = text.length()
if (self.root == nil || size <= 0)
return
end
print("\n\n Given String : ", text)
print("\n Search Word ")
i = 0
while (i < size)
# Check whether root of trie tree contain text character
if (self.root.children[(text[i]).ord - ('a').ord] != nil)
self.search_pattern(self.root, text, i, i, size, "")
end
i += 1
end
end
end
def main()
obj = Trie.new()
dictionary = ["go", "to", "tool", "old", "gold", "code", "his", "co", "good"]
size = dictionary.length
# Add dictionary element
i = 0
while (i < size)
obj.insert(dictionary[i])
i += 1
end
print("\nTrie Element\n")
obj.display(obj.root, "")
text = "wintooldgoldcogood"
obj.find_pattern(text)
end
main()
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [to] appears from 3,4
Word [tool] appears from 3,6
Word [old] appears from 5,7
Word [go] appears from 8,9
Word [gold] appears from 8,11
Word [old] appears from 9,11
Word [co] appears from 12,13
Word [go] appears from 14,15
Word [good] appears from 14,17
// Scala program
// Pattern Searching in Trie tree
class Node(var stop: Boolean , var children: Array[Node])
{
def this()
{
this(false, Array.fill[Node](26)(null));
}
}
class Trie(var root: Node)
{
def this()
{
this(new Node());
}
// This function are handles the request to add element in tire
def insert(text: String): Unit = {
// First get the length of text
var length: Int = text.length();
// This variable are used to task find the index location of character
var index: Int = 0;
// Get the root node
var head: Node = this.root;
var level: Int = 0;
while (level < length)
{
// Get the index
index = text(level) - 'a';
if (head.children(index) == null)
{
// When need to add new Node
head.children(index) = new Node();
}
head = head.children(index);
level += 1;
}
if (head != null)
{
// Indicates end of string
head.stop = true;
}
}
// This is display the elements of trie tree
def display(head: Node, about: String): Unit = {
if (head != null)
{
if (head.stop == true)
{
print("\n" + about);
}
var i: Int = 0;
while (i < 26)
{
if (head.children(i) != null)
{
this.display(head.children(i), about + (((i + 'a')).toChar));
}
i += 1;
}
}
}
// Pattern Searching
def search_pattern(head: Node, text: String, start: Int, i: Int, size: Int, result: String): Unit = {
if (head != null && i < size && head.children(text(i) - 'a') != null)
{
var node: Node = head.children(text(i) - 'a');
var ans: String = result + text(i);
if (node.stop == true)
{
// When tire words are completing
print("\n Word [" + ans + "] appears from " + start + "," + i);
}
this.search_pattern(node, text, start, i + 1, size, ans);
}
}
// Handles the request of finding given text pattern in trie tree
def find_pattern(text: String): Unit = {
var size: Int = text.length();
if (this.root == null || size <= 0)
{
return;
}
print("\n\n Given String : " + text);
print("\n Search Word ");
var i: Int = 0;
while (i < size)
{
// Check whether root of trie tree contain text character
if (this.root.children(text(i) - 'a') != null)
{
this.search_pattern(this.root, text, i, i, size, "");
}
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: Trie = new Trie();
var dictionary: Array[String] = Array("go", "to", "tool", "old", "gold", "code", "his", "co", "good");
var size: Int = dictionary.length;
// Add dictionary element
var i: Int = 0;
while (i < size)
{
obj.insert(dictionary(i));
i += 1;
}
print("\nTrie Element\n");
obj.display(obj.root, "");
var text: String = "wintooldgoldcogood";
obj.find_pattern(text);
}
}
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [to] appears from 3,4
Word [tool] appears from 3,6
Word [old] appears from 5,7
Word [go] appears from 8,9
Word [gold] appears from 8,11
Word [old] appears from 9,11
Word [co] appears from 12,13
Word [go] appears from 14,15
Word [good] appears from 14,17
// Swift 4 program
// Pattern Searching in Trie tree
class Node
{
// Indicates end of string
var stop: Bool;
var children: [Node? ];
init()
{
self.stop = false;
self.children = Array(repeating: nil, count: 26);
}
}
class Trie
{
var root: Node? ;
init()
{
self.root = Node();
}
// This function are handles the request to add element in tire
func insert(_ data: String)
{
var text = Array(data);
// First get the length of text
let length: Int = text.count;
// This variable are used to task find the index location of character
var index: Int = 0;
// Get the root node
var head: Node? = self.root;
var level: Int = 0;
var ch : String = " ";
while (level < length)
{
ch = String(text[level]);
// Get the index
index = Int(UnicodeScalar(ch)!.value) - Int(UnicodeScalar("a")!.value);
if (index < 26 && head!.children[index] == nil)
{
// When need to add new Node
head!.children[index] = Node();
}
head = head!.children[index];
level += 1;
}
if (head != nil)
{
// Indicates end of string
head!.stop = true;
}
}
// This is display the elements of trie tree
func display(_ head: Node? , _ about : String)
{
if (head != nil)
{
if (head!.stop == true)
{
print("\n", about, terminator: "");
}
var i: Int = 0;
while (i < 26)
{
if (head!.children[i] != nil)
{
self.display(head!.children[i], about + (String(UnicodeScalar(UInt8((i + 97))))));
}
i += 1;
}
}
}
// Pattern Searching
func search_pattern(_ head: Node? , _ text : [Character], _ start: Int, _ i: Int, _ size: Int, _ result: String)
{
if(i >= text.count)
{
return;
}
let ch = String(text[i]);
// Get the index
let index = Int(UnicodeScalar(ch)!.value) - Int(UnicodeScalar("a")!.value);
if (index < 26 && head != nil && i < size && head!.children[index] != nil)
{
let node: Node? = head!.children[index];
let ans: String = result + String(text[i]);
if (node!.stop == true)
{
// When tire words are completing
print("\n Word [", ans ,"] appears from ", start ,",", i, terminator: "");
}
self.search_pattern(node, text, start, i + 1, size, ans);
}
}
// Handles the request of finding given text pattern in trie tree
func find_pattern(_ data: String)
{
var text = Array(data);
let size: Int = data.count;
if (self.root == nil || size <= 0)
{
return;
}
print("\n\n Given String : ", data, terminator: "");
print("\n Search Word ", terminator: "");
var i: Int = 0;
var index: Int = 0;
var ch : String = " ";
while (i < size)
{
ch = String(text[i]);
// Get the index
index = Int(UnicodeScalar(ch)!.value) - Int(UnicodeScalar("a")!.value);
// Check whether root of trie tree contain text character
if (index < 26 && self.root!.children[index] != nil)
{
self.search_pattern(self.root, text, i, i, size, "");
}
i += 1;
}
}
}
func main()
{
let obj: Trie = Trie();
let dictionary: [String] = ["go", "to", "tool", "old", "gold", "code", "his", "co", "good"];
let size: Int = dictionary.count;
// Add dictionary element
var i: Int = 0;
while (i < size)
{
obj.insert(dictionary[i]);
i += 1;
}
print("\nTrie Element\n", terminator: "");
obj.display(obj.root, "");
let text: String = "wintooldgoldcogood";
obj.find_pattern(text);
}
main();
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [ to ] appears from 3 , 4
Word [ tool ] appears from 3 , 6
Word [ old ] appears from 5 , 7
Word [ go ] appears from 8 , 9
Word [ gold ] appears from 8 , 11
Word [ old ] appears from 9 , 11
Word [ co ] appears from 12 , 13
Word [ go ] appears from 14 , 15
Word [ good ] appears from 14 , 17
// Kotlin program
// Pattern Searching in Trie tree
class Node
{
var stop: Boolean;
var children: Array <Node?> ;
constructor()
{
this.stop = false;
this.children = Array(26){null};
}
}
class Trie
{
var root: Node;
constructor()
{
this.root = Node();
}
// This function are handles the request to add element in tire
fun insert(text: String): Unit
{
// First get the length of text
var length: Int = text.count();
// This variable are used to task find the index location of character
var index: Int ;
// Get the root node
var head: Node? = this.root;
var level: Int = 0;
while (level < length )
{
// Get the index
index = text[level] - 'a';
if (head!!.children[index] == null)
{
// When need to add new Node
head.children[index] = Node();
}
head = head.children[index];
level += 1;
}
if (head != null)
{
// Indicates end of string
head.stop = true;
}
}
// This is display the elements of trie tree
fun display(head: Node ? , about : String): Unit
{
if (head != null)
{
if (head.stop == true)
{
print("\n" + about);
}
var i: Int = 0;
while (i < 26)
{
if (head.children[i] != null)
{
this.display(head.children[i], about + (i + 97).toChar());
}
i += 1;
}
}
}
// Pattern Searching
fun search_pattern(head: Node ? , text : String, start: Int, i: Int, size: Int, result: String): Unit
{
if (head != null && i < size && head.children[text[i] - 'a'] != null)
{
var node: Node ? = head.children[text[i] - 'a'];
var ans: String = result + text[i];
if (node!!.stop == true)
{
// When tire words are completing
print("\n Word [" + ans + "] appears from " + start + "," + i);
}
this.search_pattern(node, text, start, i + 1, size, ans);
}
}
// Handles the request of finding given text pattern in trie tree
fun find_pattern(text: String): Unit
{
var size: Int = text.count();
if (size <= 0)
{
return;
}
print("\n\n Given String : " + text);
print("\n Search Word ");
var i: Int = 0;
while (i < size)
{
// Check whether root of trie tree contain text character
if (this.root.children[text[i] - 'a'] != null)
{
this.search_pattern(this.root, text, i, i, size, "");
}
i += 1;
}
}
}
fun main(args: Array <String> ): Unit
{
var obj: Trie = Trie();
var dictionary: Array <String> = arrayOf("go", "to", "tool", "old", "gold", "code", "his", "co", "good");
var size: Int = dictionary.count();
// Add dictionary element
var i: Int = 0;
while (i < size)
{
obj.insert(dictionary[i]);
i += 1;
}
print("\nTrie Element\n");
obj.display(obj.root, "");
var text: String = "wintooldgoldcogood";
obj.find_pattern(text);
}
Output
Trie Element
co
code
go
gold
good
his
old
to
tool
Given String : wintooldgoldcogood
Search Word
Word [to] appears from 3,4
Word [tool] appears from 3,6
Word [old] appears from 5,7
Word [go] appears from 8,9
Word [gold] appears from 8,11
Word [old] appears from 9,11
Word [co] appears from 12,13
Word [go] appears from 14,15
Word [good] appears from 14,17
Time Complexity
- Constructing the Trie takes O(N * M), where N is the number of dictionary words and M is the average length of the words.
- Searching the Trie takes O(K * L), where K is the length of the given text and L is the average length of the dictionary words.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment