# 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

1. Construct a Trie using the dictionary words.
2. For each character in the given text, check if the current character matches the starting character of any dictionary word in the Trie.
3. If a match is found, traverse the Trie to check for the presence of the remaining characters of the dictionary word.
4. 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:
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

1. Create a Trie object and insert dictionary words into the Trie using the `insert` function.
2. For each character in the given text, if the Trie contains the corresponding character, call the `search_pattern` function.
3. Within `search_pattern`, traverse the Trie while matching characters in the text.
4. If a valid word (stop) is found in the Trie, print its occurrence and starting position.
5. 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
for (int level = 0; level < length; level++)
{
//Get the index
index = text.charAt(level) - 'a';
{
//When need to add new Node
}
}
{
//Indicates end of string
}
}
// This is display the elements of trie tree
{
{
{
}
for (int i = 0; i < 26; i++)
{
{
}
}
}
}
//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;
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
for (int level = 0; level < length; level++)
{
// Get the index
index = text[level] - 'a';
{
// When need to add new Node
}
}
{
// Indicates end of string
}
}
//  This is display the elements of trie tree
{
{
{
}
for (int i = 0; i < 26; i++)
{
{
}
}
}
}
// 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]);
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
for (int level = 0; level < length; level++)
{
// Get the index
index = text[level] - 'a';
{
// When need to add new Node
}
}
{
// Indicates end of string
}
}
//  This is display the elements of trie tree
{
{
{
}
for (int i = 0; i < 26; i++)
{
{
}
}
}
}
// 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;
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
for (\$level = 0; \$level < \$length; \$level++)
{
// Get the index
\$index = ord(\$text[\$level]) - ord('a');
{
// When need to add new Node
}
}
{
// Indicates end of string
}
}
//  This is display the elements of trie tree
{
{
{
}
for (\$i = 0; \$i < 26; \$i++)
{
{
}
}
}
}
// 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)
{
\$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);
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
for (var level = 0; level < length; level++)
{
// Get the index
index = (text[level]).charCodeAt(0) - ('a').charCodeAt(0);
{
// When need to add new Node
}
}
{
// Indicates end of string
}
}
//  This is display the elements of trie tree
{
{
{
}
for (var i = 0; i < 26; i++)
{
{
}
}
}
}
// 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;
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
level = 0
while (level < length) :
#  Get the index
index = ord(text[level]) - ord('a')
#  When need to add new Node

level += 1

#  Indicates end of string

#   This is display the elements of trie tree

i = 0
while (i < 26) :

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) :
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)
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_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_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
level = 0
while (level < length)
#  Get the index
index = (text[level]).ord - ('a').ord
#  When need to add new Node
end

level += 1
end

#  Indicates end of string
end

end

#   This is display the elements of trie tree
end

i = 0
while (i < 26)
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)
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
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 level: Int = 0;
while (level < length)
{
//  Get the index
index = text(level) - 'a';
{
//  When need to add new Node
}
level += 1;
}
{
//  Indicates end of string
}
}
//   This is display the elements of trie tree
{
{
}
var i: Int = 0;
while (i < 26)
{
{
}
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;
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 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
}
level += 1;
}
{
//  Indicates end of string
}
}
//   This is display the elements of trie tree
{
{
{
}
var i: Int = 0;
while (i < 26)
{
{
}
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 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;
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 level: Int = 0;
while (level < length )
{
//  Get the index
index = text[level] - 'a';
{
//  When need to add new Node
}
level += 1;
}
{
//  Indicates end of string
}
}
//   This is display the elements of trie tree
{
{
{
}
var i: Int = 0;
while (i < 26)
{
{
}
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();
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.

## Comment

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.