Find the longest common prefix using Trie

Here given code implementation process.

//C++ program
//Find the Longest Common Prefix using Trie

#include<iostream>

#include<string>

#define ALPHABETS 26
using namespace std;
class Node {
  public:
    bool end;
  Node *children[ALPHABETS];
  Node() {
    this->end = false;
    for (int i = 0; i < ALPHABETS; ++i) {
      this->children[i] = NULL;
    }
  }
};
class Trie {
  public:
    Node *root;
  Trie() {
    this->root = new Node();
  }
  void insert(string text) {
    int length = text.size();
    int index = 0;
    Node *head = this->root;
    for (int level = 0; level < length; level++) {
      index = text[level] - 'a';
      if (head->children[index] == NULL) {
        head->children[index] = new Node();
      }
      head = head->children[index];
    }
    if (head != NULL) {
      head->end = true;
    }
  }
  void longestPrefix(Node *head, int same) {
    if (head != NULL) {
      int location = -1;
      bool status = true;
      for (int i = 0; i < ALPHABETS && status; i++) {
        if (head->children[i] != NULL) {
          if (location == -1) {
            location = i;
          }
          if (i != location) {
            status = false;
          }

        }
      }
      if (status == true) {
        cout << ((char)(location + 97));
        this->longestPrefix(head->children[location], same + 1);
      } else if (status == false && same == 0) {
        cout << "No Longest Prefix" << endl;
      }

    }
  }
};
int main() {
  Trie obj;
  //Insert following data
  obj.insert("cool");
  obj.insert("coder");
  obj.insert("confirm");
  obj.insert("cow");

  obj.longestPrefix(obj.root, 0);
  cout << endl;
}

Output

co

/*
  Java program
  Find the Longest Common Prefix using Trie
*/

class Node {
  //Indicates end of string
  public boolean end;

  public Node[] children;

  public Node(int size) {
    end = false;
    children = new Node[size];
  }
}
public class Trie 
{ 
  public int ALPHABETS = 26;
  public Node root; 

  public Trie()
  {
    root = new Node(ALPHABETS);
  }

  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 = 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(ALPHABETS);
      }

      head = head.children[index];
    }
    if(head != null)
    {  
      //indicates end of string
      head.end = true;
    }
  }
  public void longestPrefix(Node head,int same)
  {
    if (head != null) {
      int location = -1;
      boolean status = true;
      for (int i = 0; i < ALPHABETS && status; i++) {
        if (head.children[i] != null) {
          if (location == -1) {
            location = i;
          }
          if (i != location) {
            status = false;
          }

        }
      }
      if (status == true) {
        System.out.print((char)(location+97));
        longestPrefix(head.children[location], same + 1);
      } else if (status == false && same == 0) {
       
        System.out.print("No Longest Prefix");
      }

    }
    
  }
 
  public static void main(String[] args) 
  {
    //Make object
    Trie obj = new Trie();

   
    obj.insert("cool");
    obj.insert("coder");
    obj.insert("confirm");
    obj.insert("cow");
    
    obj.longestPrefix(obj.root,0);
    System.out.println();
  }
}

Output

co

/*
  C# program
  Find the Longest Common Prefix using Trie
*/
using System;
public class Node {
	//Indicates end of string
	public Boolean end;

	public Node[] children;

	public Node(int size) {
		end = false;
		children = new Node[size];
	}
}
public class Trie 
{ 
	public int ALPHABETS = 26;
	public Node root; 

	public Trie()
	{
		root = new Node(ALPHABETS);
	}

	public void insert(String text) {
		//first get the.Length of text
		int size = text.Length;

		//This variable are used to task find the index location of character
		int index = 0;

		//get the root node
		Node head = root;

		for (int level = 0; level < size; level++) {
			//Get the index
			index = text[level] - 'a';

			if (head.children[index] == null) {
				//When need to add new Node
				head.children[index] = new Node(ALPHABETS);
			}

			head = head.children[index];
		}
		if (head != null) {
			//indicates end of string
			head.end = true;
		}
	}
	public void longestPrefix(Node head,int same)
	{
		if (head != null) {
			int location = -1;
			Boolean status = true;
			for (int i = 0; i < ALPHABETS && status; i++) {
				if (head.children[i] != null) {
					if (location == -1) {
						location = i;
					}
					if (i != location) {
						status = false;
					}

				}
			}
			if (status == true) {
				Console.Write((char)(location+97));
				longestPrefix(head.children[location], same + 1);
			} else if (status == false && same == 0) {

				Console.Write("No Longest Prefix");
			}

		}

	}

	public static void Main(String[] args) 
	{
		//Make object
		Trie obj = new Trie();


		obj.insert("cool");
		obj.insert("coder");
		obj.insert("confirm");
		obj.insert("cow");

		obj.longestPrefix(obj.root,0);
		Console.WriteLine();
	}
}

Output

co

# Ruby Program
# Find the Longest Common Prefix using Trie
class Node 
	attr_reader :end, :children
    attr_accessor :end, :children
	def initialize(size) 
		@end = false
		@children = Array.new(size){nil}
	end
end

class Trie 
	attr_reader :ALPHABETS, :root
    attr_accessor :ALPHABETS, :root
	def initialize() 
        @ALPHABETS = 26
		@root = Node.new(@ALPHABETS)
	end
	def insert(text) 
		length = text.length()
		location = 0
		head = @root
		level = 0
		while (level < length) 
			location = text[level].ord - 'a'.ord
			if (head.children[location] == nil) 
				head.children[location] = Node.new(@ALPHABETS)
			end
			head = head.children[location]
			level += 1
		end
		if (head != nil) 
			head.end = true
		end
	end
	def longestPrefix(head, same) 
		if (head != nil) 
			location = -1
			status = true
			i = 0
			while (i < @ALPHABETS and status==true) 
				if (head.children[i] != nil) 
					if (location == -1) 
						location = i
					elsif (i != location) 
						status = false
					end
				end
				i += 1
			end
			if (status == true) 
				print((location + 97).chr)
				self.longestPrefix(head.children[location], same + 1)
			elsif (status == false and same == 0) 
				print("No Longest Prefix")
			end
		end
	end
end
def main() 
	obj = Trie.new()
	obj.insert("cool")
	obj.insert("coder")
	obj.insert("confirm")
	obj.insert("cow")
	obj.longestPrefix(obj.root,0)
	print("\n")
end
main()

Output

co

# Python Program
# Find the Longest Common Prefix using Trie
class Node :

  def __init__(self, size) :
    self.end = False;
    self.children = [None]*size;
  

class Trie :
  

  def __init__(self) :
    self.ALPHABETS = 26;
    self.root = Node(self.ALPHABETS);
  
  def insert(self, text) :
    length = len(text)
    index = 0
    head = self.root
    level = 0
    while (level < length) :
      index = ord(text[level]) - ord('a')
      if (head.children[index] == None) :
        head.children[index] = Node(self.ALPHABETS)
      
      head = head.children[index]
      level += 1
    
    if (head != None) :
      head.end = True
     
  
  def longestPrefix(self, head, same) :
    if (head != None) :
      location = -1;
      status = True;
      i = 0;
      while (i < self.ALPHABETS and status) :
        if (head.children[i] != None) :
          if (location == -1) :
            location = i;
          
          if (i != location) :
            status = False;
          
        
        i += 1;
      
      if (status == True) :
        print(chr(location + 97),end="")
        self.longestPrefix(head.children[location], same + 1);
      elif (status == False and same == 0) :
        print("No Longest Prefix");
    
  
def main() :
  obj = Trie();
  obj.insert("cool");
  obj.insert("coder");
  obj.insert("confirm");
  obj.insert("cow");
  obj.longestPrefix(obj.root,0);
  print();
  

if __name__ == "__main__":
  main()

Output

co

/*
  Node JS Program
  Find the Longest Common Prefix using Trie
*/
class Node {

	constructor(size) {
		this.end = false;
		this.children =  new Array(size).fill(null);
	}
}
class Trie {
	
	constructor() {
		this.ALPHABETS = 26;
		this.root = new Node(this.ALPHABETS);
	}
	insert(text) {
		var length = text.length;
		var index = 0;
		var head = this.root;
		var level = 0;
		while (level < length) {
			index = text.charCodeAt(level) - 'a'.charCodeAt(0);;
			if (head.children[index] == null) {
				head.children[index] = new Node(this.ALPHABETS);
			}
			head = head.children[index];
			level++;
		}
		if (head != null) {
			head.end = true;
		}
	}
	longestPrefix(head, same) {
		if (head != null) {
			var location = -1;
			var status = true;
			var i = 0;
			while (i < this.ALPHABETS && status) {
				if (head.children[i] != null) {
					if (location == -1) {
						location = i;
					}
					if (i != location) {
						status = false;
					}
				}
				i++;
			}
			if (status == true) {
				process.stdout.write(String.fromCharCode(location + 97));
				this.longestPrefix(head.children[location], same + 1);
			} else
			if (status == false && same == 0) {
				process.stdout.write("No Longest Prefix");
			}
		}
	}
}

function main() {
	var obj = new Trie();
	obj.insert("cool");
	obj.insert("coder");
	obj.insert("confirm");
	obj.insert("cow");
	obj.longestPrefix(obj.root,0);
	process.stdout.write("\n");
}
main();

Output

co

<?php
/*
  Php Program
  Find the Longest Common Prefix using Trie
*/
class Node {
  public $end;
  public $children;

  function __construct($size) {
    $this->end = false;
    $this->children = array_fill(0, $size, null);
  }
}
class Trie {
  public $ALPHABETS = 26;
  public $root;

  function __construct() {
    $this->root = new Node($this->ALPHABETS);
  }
  public  function insert($text) {
    $length = strlen($text);
    $index = 0;
    $head = $this->root;
    $level = 0;
    while ($level < $length) {
      $index = ord($text[$level]) - ord('a');
      if ($head->children[$index] == null) {
        $head->children[$index] = new Node($this->ALPHABETS);
      }
      $head = $head->children[$index];
      $level++;
    }
    if ($head != null) {
      $head->end = true;
    }
  }
  public function longestPrefix($head, $same) {
    if ($head != null) {
      $location = -1;
      $status = true;
      $i = 0;
      while ($i < $this->ALPHABETS && $status) {
        if ($head->children[$i] != null) {
          if ($location == -1) {
            $location = $i;
          }
          if ($i != $location) {
            $status = false;
          }
        }
        $i++;
      }
      if ($status == true) {
        echo(chr($location + 97));
        $this->longestPrefix($head->children[$location], $same + 1);
      } else
      if ($status == false && $same == 0) {
        echo("No Longest Prefix");
      }
    }
  
  }
}
function main() {
    $obj = new Trie();
    $obj->insert("cool");
    $obj->insert("coder");
    $obj->insert("confirm");
    $obj->insert("cow");
    $obj->longestPrefix($obj->root,0);
    echo ("\n");
}
main();

Output

co

« Previous Next »

Tree

AVL Tree Insertion

AVL Tree Deletion

AVL tree with duplicate key

Splay tree insertion

Splay tree deletion

Trie insertion

Display trie tree elements

Trie Deletion

Trie Search Word Element

Trie Bottom Up Traversal

Count Total words in Trie

Red Black Tree insertion

Red Black tree node deletion

Find duplicate rows in a binary matrix

Find the longest common prefix using Trie

Find a longest length word in Trie

Implement Leftist Tree

Fenwick Tree

Pattern Searching in Trie tree

B Tree node insertion

K dimensional tree insertion

Find the minimum in K dimensional tree

Node deletion in K dimensional tree

Construct segment tree from array

Segment tree update query

Implement B + Tree

N ary tree implementation

Find the all Kth ancestor nodes in an N-ary tree

Print the all leaf nodes in N-ary tree

Find height of n-ary tree

Minimum value node having maximum depth in an N-ary Tree

Replace every node with depth in n-ary tree

Treap implementation

Implement interval tree

Ternary Search Tree Insertion

Huffman Tree Example

Ternary Search Tree Deletion

Suffix tree implementation

Score of parentheses using tree

Construct N Level Calkin-Wilf Tree

Sort array with repeated element using AVL Tree

Count the number of words with given prefix using Trie

Find shortest unique prefix for every word in a given list

Iterative n-ary tree preorder traversal

Level order traversal of n-ary tree

Post order traversal of n-ary tree

Remove all leaf nodes from an n-ary tree

Difference between sums of odd and even levels in n-ary tree

Sum of all leaf nodes from a N-ary Tree

Radix tree implementation

Implementation trie tree with memory optimization

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

Name