Longest common prefix using divide and conquer algorithm
Here given code implementation process.
/*
Java program for
Longest common prefix using divide and conquer algorithm
*/
public class Prefix
{
// Returns the common prefix of two string
String commonPrefix(String s1,String s2)
{
String result = "";
int i = 0;
int n = s1.length();
if(s2.length() < n)
{
// Got s2 length because it is smaller to s1
n = s2.length();
}
while(i < n && s1.charAt(i) == s2.charAt(i))
{
result = result + s1.charAt(i);
i++;
}
return result;
}
String longestCommonPrefix(String arr[], int start, int ends)
{
if (start == ends)
{
return (arr[start]);
}
if(start > ends)
{
return "";
}
// Get middle of subarray
int mid = start + (ends - start) / 2;
String s1 = longestCommonPrefix(arr, start, mid);
String s2 = longestCommonPrefix(arr, mid+1, ends);
// Return common of s1 and s2
return commonPrefix(s1, s2);
}
public static void main(String[] args)
{
Prefix task = new Prefix();
String []arr = {"cool", "coder", "confirm", "cow"};
int n = arr.length;
String ans = task.longestCommonPrefix(arr,0,n-1);
System.out.print(" Longest Common Prefix is : "+ans);
}
}
Output
Longest Common Prefix is : co
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
public:
// Returns the common prefix of two string
string commonPrefix(string s1, string s2)
{
string result = "";
int i = 0;
int n = s1.length();
if (s2.length() < n)
{
// Got s2 length because it is smaller to s1
n = s2.length();
}
while (i < n && s1[i] == s2[i])
{
result = result + s1[i];
i++;
}
return result;
}
string longestCommonPrefix(string arr[], int start, int ends)
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
int mid = start + (ends - start) / 2;
string s1 = this->longestCommonPrefix(arr, start, mid);
string s2 = this->longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return this->commonPrefix(s1, s2);
}
};
int main()
{
Prefix *task = new Prefix();
string arr[] = {
"cool" , "coder" , "confirm" , "cow"
};
int n = sizeof(arr) / sizeof(arr[0]);
string ans = task->longestCommonPrefix(arr, 0, n - 1);
cout << " Longest Common Prefix is : " << ans;
return 0;
}
Output
Longest Common Prefix is : co
// Include namespace system
using System;
/*
Csharp program for
Longest common prefix using divide and conquer algorithm
*/
public class Prefix
{
// Returns the common prefix of two string
String commonPrefix(String s1, String s2)
{
String result = "";
int i = 0;
int n = s1.Length;
if (s2.Length < n)
{
// Got s2 length because it is smaller to s1
n = s2.Length;
}
while (i < n && s1[i] == s2[i])
{
result = result + s1[i];
i++;
}
return result;
}
String longestCommonPrefix(String[] arr, int start, int ends)
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
int mid = start + (ends - start) / 2;
String s1 = this.longestCommonPrefix(arr, start, mid);
String s2 = this.longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return this.commonPrefix(s1, s2);
}
public static void Main(String[] args)
{
Prefix task = new Prefix();
String[] arr = {
"cool" , "coder" , "confirm" , "cow"
};
int n = arr.Length;
String ans = task.longestCommonPrefix(arr, 0, n - 1);
Console.Write(" Longest Common Prefix is : " + ans);
}
}
Output
Longest Common Prefix is : co
package main
import "fmt"
/*
Go program for
Longest common prefix using divide and conquer algorithm
*/
// Returns the common prefix of two string
func commonPrefix(s1, s2 string) string {
var result string = ""
var i int = 0
var n int = len(s1)
if len(s2) < n {
// Got s2 length because it is smaller to s1
n = len(s2)
}
for (i < n && s1[i] == s2[i]) {
result = result +string(s1[i])
i++
}
return result
}
func longestCommonPrefix(arr[] string, start int, ends int) string {
if start == ends {
return (arr[start])
}
if start > ends {
return ""
}
// Get middle of subarray
var mid int = start + (ends - start) / 2
var s1 string = longestCommonPrefix(arr, start, mid)
var s2 string = longestCommonPrefix(arr, mid + 1, ends)
// Return common of s1 and s2
return commonPrefix(s1, s2)
}
func main() {
var arr = [] string {"cool","coder","confirm","cow"}
var n int = len(arr)
var ans string = longestCommonPrefix(arr, 0, n - 1)
fmt.Print(" Longest Common Prefix is : ", ans)
}
Output
Longest Common Prefix is : co
<?php
/*
Php program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
// Returns the common prefix of two string
function commonPrefix($s1, $s2)
{
$result = "";
$i = 0;
$n = strlen($s1);
if (strlen($s2) < $n)
{
// Got s2 length because it is smaller to s1
$n = strlen($s2);
}
while ($i < $n && $s1[$i] == $s2[$i])
{
$result = $result.strval($s1[$i]);
$i++;
}
return $result;
}
function longestCommonPrefix($arr, $start, $ends)
{
if ($start == $ends)
{
return ($arr[$start]);
}
if ($start > $ends)
{
return "";
}
// Get middle of subarray
$mid = $start + (int)(($ends - $start) / 2);
$s1 = $this->longestCommonPrefix($arr, $start, $mid);
$s2 = $this->longestCommonPrefix($arr, $mid + 1, $ends);
// Return common of s1 and s2
return $this->commonPrefix($s1, $s2);
}
}
function main()
{
$task = new Prefix();
$arr = array("cool", "coder", "confirm", "cow");
$n = count($arr);
$ans = $task->longestCommonPrefix($arr, 0, $n - 1);
echo(" Longest Common Prefix is : ".$ans);
}
main();
Output
Longest Common Prefix is : co
/*
Node JS program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
// Returns the common prefix of two string
commonPrefix(s1, s2)
{
var result = "";
var i = 0;
var n = s1.length;
if (s2.length < n)
{
// Got s2 length because it is smaller to s1
n = s2.length;
}
while (i < n && s1.charAt(i) == s2.charAt(i))
{
result = result + s1.charAt(i);
i++;
}
return result;
}
longestCommonPrefix(arr, start, ends)
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
var mid = start + parseInt((ends - start) / 2);
var s1 = this.longestCommonPrefix(arr, start, mid);
var s2 = this.longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return this.commonPrefix(s1, s2);
}
}
function main()
{
var task = new Prefix();
var arr = ["cool", "coder", "confirm", "cow"];
var n = arr.length;
var ans = task.longestCommonPrefix(arr, 0, n - 1);
process.stdout.write(" Longest Common Prefix is : " + ans);
}
main();
Output
Longest Common Prefix is : co
# Python 3 program for
# Longest common prefix using divide and conquer algorithm
class Prefix :
# Returns the common prefix of two string
def commonPrefix(self, s1, s2) :
result = ""
i = 0
n = len(s1)
if (len(s2) < n) :
# Got s2 length because it is smaller to s1
n = len(s2)
while (i < n and s1[i] == s2[i]) :
result = result + str(s1[i])
i += 1
return result
def longestCommonPrefix(self, arr, start, ends) :
if (start == ends) :
return (arr[start])
if (start > ends) :
return ""
# Get middle of sublist
mid = start + int((ends - start) / 2)
s1 = self.longestCommonPrefix(arr, start, mid)
s2 = self.longestCommonPrefix(arr, mid + 1, ends)
# Return common of s1 and s2
return self.commonPrefix(s1, s2)
def main() :
task = Prefix()
arr = ["cool", "coder", "confirm", "cow"]
n = len(arr)
ans = task.longestCommonPrefix(arr, 0, n - 1)
print(" Longest Common Prefix is : ", ans, end = "")
if __name__ == "__main__": main()
Output
Longest Common Prefix is : co
# Ruby program for
# Longest common prefix using divide and conquer algorithm
class Prefix
# Returns the common prefix of two string
def commonPrefix(s1, s2)
result = ""
i = 0
n = s1.length
if (s2.length < n)
# Got s2 length because it is smaller to s1
n = s2.length
end
while (i < n && s1[i] == s2[i])
result = result + s1[i].to_s
i += 1
end
return result
end
def longestCommonPrefix(arr, start, ends)
if (start == ends)
return (arr[start])
end
if (start > ends)
return ""
end
# Get middle of subarray
mid = start + (ends - start) / 2
s1 = self.longestCommonPrefix(arr, start, mid)
s2 = self.longestCommonPrefix(arr, mid + 1, ends)
# Return common of s1 and s2
return self.commonPrefix(s1, s2)
end
end
def main()
task = Prefix.new()
arr = ["cool", "coder", "confirm", "cow"]
n = arr.length
ans = task.longestCommonPrefix(arr, 0, n - 1)
print(" Longest Common Prefix is : ", ans)
end
main()
Output
Longest Common Prefix is : co
/*
Scala program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix()
{
// Returns the common prefix of two string
def commonPrefix(s1: String, s2: String): String = {
var result: String = "";
var i: Int = 0;
var n: Int = s1.length();
if (s2.length() < n)
{
// Got s2 length because it is smaller to s1
n = s2.length();
}
while (i < n && s1.charAt(i) == s2.charAt(i))
{
result = result + s1.charAt(i).toString();
i += 1;
}
return result;
}
def longestCommonPrefix(arr: Array[String], start: Int, ends: Int): String = {
if (start == ends)
{
return (arr(start));
}
if (start > ends)
{
return "";
}
// Get middle of subarray
var mid: Int = start + (ends - start) / 2;
var s1: String = longestCommonPrefix(arr, start, mid);
var s2: String = longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return commonPrefix(s1, s2);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Prefix = new Prefix();
var arr: Array[String] = Array("cool", "coder", "confirm", "cow");
var n: Int = arr.length;
var ans: String = task.longestCommonPrefix(arr, 0, n - 1);
print(" Longest Common Prefix is : " + ans);
}
}
Output
Longest Common Prefix is : co
import Foundation;
/*
Swift 4 program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
// Returns the common prefix of two string
func commonPrefix(_ s1: String, _ s2: String) -> String
{
var result: String = "";
var i: Int = 0;
var n: Int = s1.count;
let t1 = Array(s1);
let t2 = Array(s2);
if (s2.count < n)
{
// Got s2 length because it is smaller to s1
n = s2.count;
}
while (i < n && t1[i] == t2[i])
{
result = result + String(t1[i]);
i += 1;
}
return result;
}
func longestCommonPrefix(
_ arr: [String],
_ start: Int,
_ ends: Int) -> String
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
let mid: Int = start + (ends - start) / 2;
let s1: String = self.longestCommonPrefix(arr, start, mid);
let s2: String = self.longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return self.commonPrefix(s1, s2);
}
}
func main()
{
let task: Prefix = Prefix();
let arr: [String] = ["cool", "coder", "confirm", "cow"];
let n: Int = arr.count;
let ans: String = task.longestCommonPrefix(arr, 0, n - 1);
print(" Longest Common Prefix is : ", ans, terminator: "");
}
main();
Output
Longest Common Prefix is : co
/*
Kotlin program for
Longest common prefix using divide and conquer algorithm
*/
class Prefix
{
// Returns the common prefix of two string
fun commonPrefix(s1: String, s2: String): String
{
var result: String = "";
var i: Int = 0;
var n: Int = s1.length;
if (s2.length < n)
{
// Got s2 length because it is smaller to s1
n = s2.length;
}
while (i < n && s1.get(i) == s2.get(i))
{
result = result + s1.get(i).toString();
i += 1;
}
return result;
}
fun longestCommonPrefix(
arr: Array < String > , start: Int, ends: Int): String
{
if (start == ends)
{
return (arr[start]);
}
if (start > ends)
{
return "";
}
// Get middle of subarray
val mid: Int = start + (ends - start) / 2;
val s1: String = this.longestCommonPrefix(arr, start, mid);
val s2: String = this.longestCommonPrefix(arr, mid + 1, ends);
// Return common of s1 and s2
return this.commonPrefix(s1, s2);
}
}
fun main(args: Array < String > ): Unit
{
val task: Prefix = Prefix();
val arr: Array < String > = arrayOf("cool", "coder", "confirm", "cow");
val n: Int = arr.count();
val ans: String = task.longestCommonPrefix(arr, 0, n - 1);
print(" Longest Common Prefix is : " + ans);
}
Output
Longest Common Prefix is : 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