Longest common prefix using divide and conquer algorithm
Divide and Conquer is a widely used algorithmic paradigm that breaks down a problem into subproblems, solves them independently, and combines the solutions to solve the original problem. In this article, we will explore the Divide and Conquer approach to find the Longest Common Prefix (LCP) among a set of strings.
Problem Statement
Given an array of strings, we want to find the longest common prefix that is shared by all the strings. For example, if the input array is ["cool", "coder", "confirm", "cow"], the longest common prefix is "co".
Pseudocode Algorithm
String commonPrefix(String s1, String s2):
result = ""
i = 0
n = min(s1.length(), s2.length())
while i < n and s1.charAt(i) == s2.charAt(i):
result = result + s1.charAt(i)
i = i + 1
return result
String longestCommonPrefix(String arr[], int start, int end):
if start == end:
return arr[start]
if start > end:
return ""
mid = start + (end - start) / 2
s1 = longestCommonPrefix(arr, start, mid)
s2 = longestCommonPrefix(arr, mid + 1, end)
return commonPrefix(s1, s2)
The algorithm consists of two main functions:
commonPrefix
: This function finds the common prefix between two stringss1
ands2
. It iterates through the characters of the strings until it finds a mismatch or reaches the end of the shorter string.longestCommonPrefix
: This function recursively divides the input array into two halves until there is only one string left. It then combines the common prefixes of the left and right halves using thecommonPrefix
function.
Code Solution
/*
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
Explanation
Let's walk through the code to understand how it works:
- We start by defining the
commonPrefix
function. It takes two strings,s1
ands2
, as input. We initialize an empty string calledresult
to store the common prefix. - We compare the characters of
s1
ands2
at each position. If they are equal, we append the character toresult
and increment the indexi
. - We continue this process until we reach the end of either string or find a mismatch.
- The
commonPrefix
function returns the resulting string. - Next, we define the
longestCommonPrefix
function. It takes an array of strings,arr
, and the start and end indices as input. - If the start and end indices are the same, we return the string at that index. This serves as the base case for the recursion.
- If the start index is greater than the end index, it means we have an empty array, so we return an empty string.
- We calculate the middle index,
mid
, and recursively calllongestCommonPrefix
on the left and right halves of the array. - We combine the common prefixes of the left and right halves using the
commonPrefix
function. - The resulting common prefix is returned as the output of the
longestCommonPrefix
function.
The main function creates an instance of the Prefix
class and initializes an array of strings. It calls the longestCommonPrefix
function with the array and the range of indices. Finally, it prints the resulting longest common prefix.
Output Explanation
The output of the given code is "co". It correctly identifies the longest common prefix among the strings "cool", "coder", "confirm", and "cow".
Time Complexity
The time complexity of this algorithm can be analyzed as follows:
- Let
n
be the number of strings in the input array, and letm
be the length of the longest string. - The
commonPrefix
function takes O(m) time to compare the characters of two strings. - The
longestCommonPrefix
function recursively divides the input array into two halves until there is only one string left. This process takes O(log n) iterations. - At each iteration, the
commonPrefix
function is called on two strings, which takes O(m) time.
Therefore, the overall time complexity of the algorithm is O(m * log n).
Finally
In this article, we explored the Divide and Conquer approach to finding the Longest Common Prefix (LCP) among a set of strings. We discussed the problem statement, provided a detailed explanation of the pseudocode algorithm, and analyzed its time complexity. The code implementation in Java was also provided, along with an explanation of the output.
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