Skip to main content

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:
            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

  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
        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.
Last updated on by Kalkicode




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.

New Comment