Home » Interview Questions » String Interview Questions » Longest Common Prefix (Using Biary Search)

Longest Common Prefix (Using Biary Search)


()

Given a array of strings, write a function that will print the longest common prefix If there is no common prefix then print “No Common Prefix”

Example

INPUT
arr[] = {“boy”, ‘boyfriend”, “bo”}

OUTPUT
“bo”

Algorithm(using Binary search)

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 left half are present at the corresponding indexes, then add the characters to the output stirng and search in right half to find the longer prefix

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

C++ Program

#include<bits/stdc++.h>
using namespace std;
 
// finds the minimum length
int minLength(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);
}
//checks if the input array contains this prefix 
bool checkPrefix(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);
}
 
// returns the longest common prefix
string longestCommonPrefix(string arr[], int n)
{
    int index = minLength(arr, n);
    string prefix; // Our resultant string
 
    //Binary search
    int low = 0, high = index;
 
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
 
        if (checkPrefix (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);
 
            // right part
            low = mid + 1;
        }
 
        else // Go for the left part
            high = mid - 1;
    }
 
    return (prefix);
}
 

int main()
{
    string arr[] = {"boyfriend", "boy", "bo"};
    int n = sizeof (arr) / sizeof (arr[0]);
 
    string ans = longestCommonPrefix(arr, n);
 
    if (ans.length())
        cout << "The longest common prefix is "<< ans<<endl;
    else
        cout << "There is no common prefix";
    return (0);
}

Try It

READ  Rabin Karp Algorithm

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions