Longest Common Prefix using Divide and Conquer

Problem Statement

In the “Longest Common Prefix using Divide and Conquer ” problem, we have given an integer n and n strings. Write a program that will print the longest common prefix. If there is no common prefix then print “-1”.

Input Format

The first line contains an integer n.

Next n line containing a single string each.

Output Format

Print a string that represents the Longest Common Prefix of given strings. If no such prefix string found then print “-1”.

Constraints

• 1<=n<=10^3
• 1<=|s[i]|<=10^3 where i from 0 to n-1
• s[i][j] must be a lower case English alphabet where i from 0 to n-1 and j from 0 to |s[i]|.

Example

3
tutorial 
tutcup 
turnin

tu

Explanation: Here we can see “tu” is the prefix that presents in every string.

Algorithm for Longest Common Prefix using Divide and Conquer

In this algorithm, a divide and conquer approach is discussed. We first divide the arrays of string into two parts. Then we do the same for the left part and after that for the right part. We will do it until and unless all the strings become of length 1. Now after that, we will start conquering by returning the common prefix of the left and the right strings.

1. Recursively divide the array of strings into two parts until length becomes 1

2. Now, start conquering by returning the common prefix of the left and right strings

Implementation

C++ Program for Longest Common Prefix using Divide and Conquer

#include<bits/stdc++.h> 
using namespace std; 

string commonPrefixUtil(string str1, string str2) 
{ 
  string result; 
  int n1 = str1.length(), n2 = str2.length(); 
  for (int i=0,j=0;i<n1&&j<n2;i++,j++) 
  { 
    if(str1[i]!=str2[j]) 
    {
        break; 
    }
    result.push_back(str1[i]); 
  } 
  return result; 
} 

string commonPrefix(string s[], int x, int y) 
{ 
  if(x==y) 
  {
      return s[x]; 
  }
  if(y>x) 
  { 
    int mid=x+(y-x)/2; 
    string s1 = commonPrefix(s, x, mid); 
    string s2 = commonPrefix(s, mid+1, y); 
    return commonPrefixUtil(s1, s2); 
  } 
} 
int main() 
{ 
  int n;
  cin>>n;
  string s[n];
  for(int i=0;i<n;i++)
  {
      cin>>s[i];
  }
  string ans = commonPrefix(s,0,n-1); 
  if(ans.length()>0) 
  {
      cout<<ans<<endl;
  }
  else
  {
    cout<<-1<<endl; 
  }
  return (0); 
} 

Java Program for Longest Common Prefix using Divide and Conquer

import java.util.Scanner;

class sum { 
    
  static String commonPrefixUtil(String str1, String str2) { 
    String result = ""; 
    int n1 = str1.length(), n2 = str2.length(); 
    for (int i = 0, j = 0; i <= n1 - 1 && j <= n2 - 1; i++, j++) 
                { 
      if(str1.charAt(i)!=str2.charAt(j)) 
                        { 
        break; 
      } 
      result += str1.charAt(i); 
    } 
    return result; 
  } 
  static String commonPrefix(String s[], int x, int y) { 
    if(x==y) 
                { 
                    return s[x]; 
    } 
    if(y>x) 
                { 
      int mid = x + (y-x)/2; 
      String s1 = commonPrefix(s, x, mid); 
      String s2 = commonPrefix(s, mid + 1, y); 
      return commonPrefixUtil(s1,s2); 
    } 
    return null; 
  } 
  public static void main(String[] args) 
        {
            Scanner sr = new Scanner(System.in);
            int n = sr.nextInt();
            String s[] = new String[n];
            for(int i=0;i<n;i++)
            {
                s[i]= sr.next();
            }
      String ans = commonPrefix(s,0,n-1); 
      if(ans.length()!=0) 
            { 
                System.out.println(ans); 
            } 
            else 
            { 
                System.out.println("-1"); 
            } 
  } 
} 

3
car 
carrace 
caramazing

car

Complexity Analysis for Longest Common Prefix using Divide and Conquer

Time Complexity

O(n*m) where n is the number of the strings and m is the length of the maximum string. Here we visit every character that’s why time complexity is O(n*m).

Space Complexity

O(m*logn) because we storing the resultant string or the longest prefix string we are allocating space which is O(m*logn).