How to find the longest common prefix in an array of strings

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”.

Method 1 (Horizontal scanning)

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 array
    std::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;
}

Method 2 - Binary search

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.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits> // Include for INT_MAX
using namespace std;
int main() {
    vector<string> arr = {"mint", "mini", "mineral"};
    // Find the length of the shortest string
    int 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 strings
        bool 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;
        else
            high = mid - 1;
    }
    // Extract the longest common prefix found
    string result = arr[0].substr(0, low);
    cout << "Longest common prefix: " << result << endl;
    return 0;
}

Free Resources