Home » Interview Questions » String Interview Questions » Longest Common Prefix (Using Divide and Conquer)

Longest Common Prefix (Using Divide and Conquer)


()

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”

Time Complexity : O(mn), where m is the length of the largest string and n is the numbe rof strings

Algorithm

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

C++ Program

#include<bits/stdc++.h>
using namespace std;
 
//Finds the common prefix between two strings
string commonPrefix(string s1, string s2)
{
    string result;
    int n1 = s1.length(), n2 = s2.length();
 
    for (int i=0, j=0; i<=n1-1&&j<=n2-1; i++,j++)
    {
        if (s1[i] != s2[j])
            break;
        result.push_back(s1[i]);
    }
    return (result);
}
 
//returns the prefix of the longest common prefix, recursisve functio
string longestCommonPrefix(string arr[], int low, int high)
{
    if (low == high)
        return (arr[low]);
 
    if (high > low)
    {
        int mid = low + (high - low) / 2;
 
        string s1 = longestCommonPrefix(arr, low, mid);
        string s2 = longestCommonPrefix(arr, mid+1, high);
 
        return (commonPrefix(s1, s2));
    }
}
 

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

Try It

 

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