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

 


Next > < Prev
Scroll to Top