Question

How to find the longest common string prefix in array of strings in C++

Answer 1

#include <iostream>
#include <algorithm>

int main() {
    std::string arr[] = {"cartography", "carburettor", "carbonating"}; 
    int size = sizeof(arr)/sizeof(*arr);

    std::sort(arr, arr + size);
    std::cout << arr[0] << " " << arr[1] << " " << arr[2] << "\n";
    
    int length = arr[0].size();
    std::string common_prefix = "";

    for (int i = 0; i < length; i++){
      std::cout << arr[0][i] << " " << arr[size - 1][i] << "\n";      
      std::cout << arr[0] << " " << arr[size - 1] << "\n";
      if (arr[0][i] == arr[size - 1][I]) {
        common_prefix += arr[0][i];
      }
      else {
        break;
      }
    }
    std::cout << "Longest common prefix: " << common_prefix;

    return 0;
}



/*
run:

carbonating carburettor cartography
c c
carbonating cartography
a a
carbonating cartography
r r
carbonating cartography
b t
carbonating cartography
Longest common prefix: car

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <algorithm>

std::string longestCommonPrefix(std::string arr[], int size) { 
    if (size == 0) 
        return ""; 
  
    if (size == 1) 
        return arr[0]; 

    sort(arr, arr + size); 

    int min_length = std::min(arr[0].size(), arr[size - 1].size()); 
    std::string first = arr[0], last = arr[size - 1]; 
    int i = 0; 
    while (i < min_length && first[i] == last[i]) 
        i++; 
  
    return first.substr(0, i); 
} 

int main() {
    std::string arr[] = {"cartography", "carburettor", "carbonating"}; 

    std::cout << "Longest common prefix: " << longestCommonPrefix(arr, sizeof(arr)/sizeof(*arr));

    return 0;
}



/*
run:

Longest common prefix: car

*/

 

70+ SQL courses for beginners and professionals