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