Skip to main content

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