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
