A prefix is a collection of characters at the beginning of a string. For instance, “mi” is a prefix of “mint” and the longest common prefix between “mint”, “mini”, and “mineral” is “min”.
Sort the array of strings in alphabetical order.
Compare the characters in the first and last strings in the array. Since the array is sorted, common characters among the first and last element will be common among all the elements of the array.
2.1. If they are same, then append the character to the result
.
2.2. Else, stop the comparison – result
contains the longest common prefix among the strings in the array.
The following illustration shows the algorithm in action:
#include <iostream>#include <string>#include <algorithm>#include <string>using namespace std;int main() {string arr[3] = {"mint", "mini", "mineral"};int size = sizeof(arr)/sizeof(*arr);// The longest common prefix of an empty array is "".if (size == 0){cout << "Longest common prefix:" << "" <<endl;}// The longest common prefix of an array containing// only one element is that element itself.else if (size == 1){cout << "Longest common prefix:" << arr[0] <<endl;}else{// Sort the arraystd::sort(arr, arr + size);int length = arr[0].size();string result = "";// Compare the first and the last string character// by character.for(int i = 0; i < length; i++){// If the characters match, append the character to the result.if(arr[0][i] == arr[size-1][i]){result += arr[0][i];}// Else stop the comparison.else{break;}}cout << "Longest common prefix: " << result <<endl;}return 0;}
First find the length of the shortest string present in an array.
Intialize two variables, variable low
to 0 and variable high
to the last element which is length - 1.
Iterate while low
<= high
and compare if the substring from index 0
to mid
of the first string is a prefix of all strings in the array. Update the low
and high
accordingly.
After completing the process, return the substring from index 0 to low
from the first string, as it will be the longest common prefix.
#include <iostream>#include <vector>#include <algorithm>#include <climits> // Include for INT_MAXusing namespace std;int main() {vector<string> arr = {"mint", "mini", "mineral"};// Find the length of the shortest stringint length = INT_MAX;for(const string& s : arr)length = min(length, (int)s.length());int low = 0, high = length - 1;while (low <= high) {int mid = (low + high) / 2;// Check if the substring from index 0 to mid is a prefix of all stringsbool allEqual = true;for(const string& s : arr) {if(s.substr(0, mid + 1) != arr[0].substr(0, mid + 1)) {allEqual = false;break;}}if(allEqual)low = mid + 1;elsehigh = mid - 1;}// Extract the longest common prefix foundstring result = arr[0].substr(0, low);cout << "Longest common prefix: " << result << endl;return 0;}
RELATED TAGS