Pattern Searching in Trie tree
Here given code implementation process.
// 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
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