Skip to main content

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 strings s1 and s2. 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 the commonPrefix 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:

  1. We start by defining the commonPrefix function. It takes two strings, s1 and s2, as input. We initialize an empty string called result to store the common prefix.
  2. We compare the characters of s1 and s2 at each position. If they are equal, we append the character to result and increment the index i.
  3. We continue this process until we reach the end of either string or find a mismatch.
  4. The commonPrefix function returns the resulting string.
  5. Next, we define the longestCommonPrefix function. It takes an array of strings, arr, and the start and end indices as input.
  6. 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.
  7. If the start index is greater than the end index, it means we have an empty array, so we return an empty string.
  8. We calculate the middle index, mid, and recursively call longestCommonPrefix on the left and right halves of the array.
  9. We combine the common prefixes of the left and right halves using the commonPrefix function.
  10. 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 let m 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.

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