Longest Common Prefix Using Binary Search II

Problem Statement

In the “Longest Common Prefix Using Binary Search II” problem we have given an integer value N and N strings. Write a program that will print the longest common prefix of given strings. If there is no common prefix then print “-1”.

Input Format

The first line containing an integer value N which denotes the number of strings.

Next N lines containing a string.

Output Format

The first and only one line containing a string “ans” which is our Longest Common Prefix of the given N strings. If no such prefix exists 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

5
abcde 
abba 
abaa 
abbbbb 
ababab

ab

Explanation: Here we can see the common prefix of the 1st and second string is “ab”. Now check this prefix with other strings using binary search. We get the final prefix which is “ab”.

Algorithm for Longest Common Prefix Using Binary Search II

1. Find the string which has the minimum length(let it be L), and perform binary search on any one of the string from input array where Low = 0 and High = L-1

2. If all the characters in the left half are present at the corresponding indexes, then add the characters to the output stirng and search in the right half to find the longer prefix

3. Else, If the characters in the left half is not present in corresponding indexes then there is no need to search in the right half. But, keep searching in the left half(ie, start index to mid-index)

Implementation

C++ Program for Longest Common Prefix Using Binary Search II

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

int min_length(vector<string> v) 
{ 
    int n=v.size();
  int mval = INT_MAX; 

  for (int i=0; i<=n-1; i++) 
    if (v[i].length() < mval) 
      mval = v[i].length(); 
  return mval; 
} 

bool allContainsPrefix(vector<string> v, int n, string str, 
          int start, int end) 
{ 
  for (int i=0; i<=n-1; i++) 
    for (int j=start; j<=end; j++) 
      if (v[i][j] != str[j]) 
        return (false); 
  return (true); 
} 

string common_prefix(vector<string> v) 
{ 
    int n=v.size();
  int index = min_length(v); 
  string prefix; 
  int low = 0, high = index; 

  while (low <= high) 
  { 
    int mid = low + (high - low) / 2; 
    if(allContainsPrefix (v, n, v[0], low, mid)) 
    { 
      prefix = prefix + v[0].substr(low, mid-low+1); 
      low = mid + 1; 
    } 
    else 
    {
        high = mid - 1;
    }
  } 
  return prefix; 
} 

int main() 
{ 
    int n;
    cin>>n;
    vector<string> v;
    for(int i=0;i<n;i++)
    {
        string x;
        cin>>x;
        v.push_back(x);
    }
    string ans = common_prefix(v);
  if(ans.length()) 
  {
      cout<<ans<<endl;
  }
  else
  {
      cout<<-1<<endl; 
  }
  return (0); 
} 

Java Program for Longest Common Prefix Using Binary Search II

import java.util.Scanner;
import java.util.Vector;
class sum
{
    public static int findMinLength(Vector<String> v) 
    { 
        int n=v.size();
  int min = Integer.MAX_VALUE; 
  for (int i = 0; i <= (n - 1); i++) 
  { 
    if (v.get(i).length() < min) { 
      min = v.get(i).length(); 
    } 
  } 
  return min; 
    }
    public static boolean allContainsPrefix(Vector<String> v, int n, String str, int start, int end) 
  { 
    for (int i = 0; i <= (n - 1); i++) 
    { 
      String arr_i = v.get(i); 
      
      for (int j = start; j <= end; j++) 
        if (arr_i.charAt(j) != str.charAt(j)) 
          return false; 
    } 
    return true; 
  }
    public static String common_prefix(Vector<String> v)
    {
                int n=v.size();
                int index = findMinLength(v); 
    String prefix = "";
    int low = 0, high = index-1; 
    while(low <= high){ 
      int mid = low + (high - low)/2; 
      if(allContainsPrefix(v, n, v.get(0), low, mid)==true) 
      { 
        prefix = prefix + v.get(0).substring(low, mid + 1); 
        low = mid + 1; 
      } 
      else 
      { 
        high = mid - 1; 
      } 
    } 
    return prefix; 
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        Vector<String> v = new Vector<String>(n+1);
        for(int i=0;i<n;i++)
        {
            String x = sr.next();
            v.add(x);
        }
        String ans = common_prefix(v);
        if(ans.length()!=0)
        {
            System.out.println(ans);
        }
        else
        {
            System.out.println("-1");
        }
    }
}

5
abcde 
abcd 
abcdefgh 
abcqwer 
abcdhfdiefi

abc

O(m) where m is the length of the maximum string. We use this space to store the common prefix after performing an operation between strings.