Skip to main content

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