Longest Common Prefix using Binary Search
The idea is based on following observations:
- The length of common prefix cannot be greater than the smallest string in given set of strings
- Instead of find each character from start if present in all strings, we can take a possible prefix (most probably the smallest string) and check for common prefix by dividing in half.
Illustration:
- Consider strings as {“w3wiki”, “geeks”, “geek”, “geezer”}
- Smallest string given = “geek”, so the Longest common prefix possible is “geek”
- Now we start breaking this hypothesis using binary search:
- Break “geek” by finding mid.
- first half = “ge”, which is present is all given strings. So add “ge” to the actual longest common substring.
- second half = “ek”, which is not present in last string “geezer”. Hence we need to repeat the process for this string.
- Break “ek” by finding mid.
- first half = “e”, which is present is all given strings. So append “e” to the actual longest common substring.
- second half = “k”, which is not present in last string “geezer”. Hence we need to repeat the process for this string.
- Break “k” by finding mid.
- mid = “k”, which is not present in last string “geezer”. Hence we discard this.
- Now no more string is present to match.
- Therefore, Longest Common Prefix using Binary Search = “gee”
Below is the implementation of above approach.
C++
// A C++ Program to find the longest common prefix #include <bits/stdc++.h> using namespace std; // A Function to find the string having the minimum // length and returns that length int findMinLength(string arr[], int n) { int min = INT_MAX; for ( int i = 0; i <= n - 1; i++) if (arr[i].length() < min) min = arr[i].length(); return (min); } bool allContainsPrefix(string arr[], int n, string str, int start, int end) { for ( int i = 0; i <= n - 1; i++) for ( int j = start; j <= end; j++) if (arr[i][j] != str[j]) return ( false ); return ( true ); } // A Function that returns the longest common prefix // from the array of strings string commonPrefix(string arr[], int n) { int index = findMinLength(arr, n); string prefix; // Our resultant string // We will do an in-place binary search on the // first string of the array in the range 0 to // index int low = 0, high = index; while (low <= high) { // Same as (low + high)/2, but avoids overflow // for large low and high int mid = low + (high - low) / 2; if (allContainsPrefix(arr, n, arr[0], low, mid)) { // If all the strings in the input array // contains this prefix then append this // substring to our answer prefix = prefix + arr[0].substr(low, mid - low + 1); // And then go for the right part low = mid + 1; } else // Go for the left part high = mid - 1; } return (prefix); } // Driver program to test above function int main() { string arr[] = { "w3wiki" , "geeks" , "geek" , "geezer" }; int n = sizeof (arr) / sizeof (arr[0]); string ans = commonPrefix(arr, n); if (ans.length()) cout << "The longest common prefix is " << ans; else cout << "There is no common prefix" ; return (0); } |
Java
// A Java Program to find the longest common prefix class GFG { // A Function to find the string having the // minimum length and returns that length static int findMinLength(String arr[], int n) { int min = Integer.MAX_VALUE; for ( int i = 0 ; i <= (n - 1 ); i++) { if (arr[i].length() < min) { min = arr[i].length(); } } return min; } static boolean allContainsPrefix(String arr[], int n, String str, int start, int end) { for ( int i = 0 ; i <= (n - 1 ); i++) { String arr_i = arr[i]; for ( int j = start; j <= end; j++) if (arr_i.charAt(j) != str.charAt(j)) return false ; } return true ; } // A Function that returns the longest common prefix // from the array of strings static String commonPrefix(String arr[], int n) { int index = findMinLength(arr, n); String prefix = "" ; // Our resultant string // We will do an in-place binary search on the // first string of the array in the range 0 to // index int low = 0 , high = index - 1 ; while (low <= high) { // Same as (low + high)/2, but avoids // overflow for large low and high int mid = low + (high - low) / 2 ; if (allContainsPrefix(arr, n, arr[ 0 ], low, mid)) { // If all the strings in the input array // contains this prefix then append this // substring to our answer prefix = prefix + arr[ 0 ].substring(low, mid + 1 ); // And then go for the right part low = mid + 1 ; } else // Go for the left part { high = mid - 1 ; } } return prefix; } // Driver program to test above function public static void main(String args[]) { String arr[] = { "w3wiki" , "geeks" , "geek" , "geezer" }; int n = arr.length; String ans = commonPrefix(arr, n); if (ans.length() > 0 ) System.out.println( "The longest common" + " prefix is " + ans); else System.out.println( "There is no common" + " prefix" ); } } // This code is contributed by Indrajit Sinha. |
Python3
# A Python3 Program to find # the longest common prefix # A Function to find the string having the # minimum length and returns that length def findMinLength(strList): return len ( min (arr, key = len )) def allContainsPrefix(strList, str , start, end): for i in range ( 0 , len (strList)): word = strList[i] for j in range (start, end + 1 ): if word[j] ! = str [j]: return False return True # A Function that returns the longest # common prefix from the array of strings def CommonPrefix(strList): index = findMinLength(strList) prefix = "" # Our resultant string # We will do an in-place binary search # on the first string of the array # in the range 0 to index low, high = 0 , index - 1 while low < = high: # Same as (low + high)/2, but avoids # overflow for large low and high mid = int (low + (high - low) / 2 ) if allContainsPrefix(strList, strList[ 0 ], low, mid): # If all the strings in the input array # contains this prefix then append this # substring to our answer prefix = prefix + strList[ 0 ][low:mid + 1 ] # And then go for the right part low = mid + 1 else : # Go for the left part high = mid - 1 return prefix # Driver Code arr = [ "w3wiki" , "geeks" , "geek" , "geezer" ] lcp = CommonPrefix(arr) if len (lcp) > 0 : print ( "The longest common prefix is " + str (lcp)) else : print ( "There is no common prefix" ) # This code is contributed by garychan8523 |
C#
// C# Program to find the longest common prefix using // System; using System; public class GFG { // A Function to find the string having the // minimum length and returns that length static int findMinLength( string [] arr, int n) { int min = int .MaxValue; for ( int i = 0; i <= (n - 1); i++) { if (arr[i].Length < min) { min = arr[i].Length; } } return min; } static bool allContainsPrefix( string [] arr, int n, string str, int start, int end) { for ( int i = 0; i <= (n - 1); i++) { string arr_i = arr[i]; for ( int j = start; j <= end; j++) if (arr_i[j] != str[j]) return false ; } return true ; } // A Function that returns the longest common prefix // from the array of strings static string commonPrefix( string [] arr, int n) { int index = findMinLength(arr, n); string prefix = "" ; // Our resultant string // We will do an in-place binary search on the // first string of the array in the range 0 to // index int low = 0, high = index; while (low <= high) { // Same as (low + high)/2, but avoids // overflow for large low and high int mid = low + (high - low) / 2; if (allContainsPrefix(arr, n, arr[0], low, mid)) { // If all the strings in the input array // contains this prefix then append this // substring to our answer prefix = prefix + arr[0].Substring(low, mid + 1); // And then go for the right part low = mid + 1; } else // Go for the left part { high = mid - 1; } } return prefix; } // Driver program to test above function public static void Main() { string [] arr = { "w3wiki" , "geeks" , "geek" , "geezer" }; int n = arr.Length; string ans = commonPrefix(arr, n); if (ans.Length > 0) Console.WriteLine( "The longest common" + " prefix is - " + ans); else Console.WriteLine( "There is no common" + " prefix" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
// A JavaScript Program to find the longest common prefix // A Function to find the string having the minimum // length and returns that length function findMinLength( arr , n) { var min = Number.POSITIVE_INFINITY; for (let i=0; i<=n-1; i++) if (arr[i].length< min) min = arr[i].length; return (min); } function allContainsPrefix( arr, n, str, start, end) { for (let i=0; i<=n-1; i++) for (let j=start; j<=end; j++) if (arr[i][j] != str[j]) return ( false ); return ( true ); } // A Function that returns the longest common prefix // from the array of strings function commonPrefix( arr , n) { var index = findMinLength(arr, n); var prefix = "" ; // Our resultant string // We will do an in-place binary search on the // first string of the array in the range 0 to // index var low = 0, high = index; while (low <= high) { // Same as (low + high)/2, but avoids overflow // for large low and high var mid = low + (high - low) / 2; if (allContainsPrefix (arr, n, arr[0], low, mid)) { // If all the strings in the input array contains // this prefix then append this substring to // our answer prefix = prefix + arr[0].substr(low, mid-low+1); // And then go for the right part low = mid + 1; } else // Go for the left part high = mid - 1; } return (prefix); } // Driver program to test above function var arr= new Array( "w3wiki" , "geeks" , "geek" , "geezer" ); var n = arr.length; var ans = commonPrefix(arr, n); if (ans.length) console.log( "The longest common prefix is " + ans); else console.log( "There is no common prefix" ); // This code is contributed by ukasp. |
The longest common prefix is gee
Time Complexity : O(NM log M)
The recurrence relation is T(M) = T(M/2) + O(MN), where
- N = Number of strings
- M = Length of the largest string
So we can say that the time complexity is O(NM log M)
Auxiliary Space: To store the longest prefix string we are allocating space which is O(N) where, N = length of the largest string among all the strings
Longest Common Prefix using Binary Search
Given a set of strings, the tasks is to find the longest common prefix using Binary Search.
Input: str = {“w3wiki”, “geeks”, “geek”, “geezer”}
Output: “gee”
Explanation: All the given strings have “gee” prefix common in them, which is the longest them.
Input: {“apple”, “ape”, “april”}
Output: “ap”