# 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);
}``````

Scroll to Top