Programa C++ para encontrar el prefijo común más largo usando la clasificación

Declaración del problema: dado un conjunto de strings, encuentre el prefijo común más largo.
Ejemplos: 
 

Input: {"geeksforgeeks", "geeks", "geek", "geezer"}
Output: "gee"

Input: {"apple", "ape", "april"}
Output: "ap"

El prefijo común más largo para una array de strings es el prefijo común entre 2 strings más diferentes. Por ejemplo, en la array dada {“manzana”, “simio”, “cebra”}, no hay un prefijo común porque las 2 strings más diferentes de la array “simio” y “cebra” no comparten ningún carácter inicial. 
Hemos discutido cinco enfoques diferentes en las publicaciones a continuación. 
 

1. Coincidencia palabra por palabra
2. Coincidencia de personaje por personaje
3. Divide y conquistaras
4. Búsqueda binaria .
5. Usando Trie)

En esta publicación se analiza un nuevo método basado en la clasificación. La idea es ordenar la array de strings y encontrar el prefijo común de la primera y la última string de la array ordenada.
 

// C++ program to find longest common prefix 
// of given array of words.
#include<iostream>
#include<algorithm>
  
using namespace std;
  
// Function to find the longest common prefix
string longestCommonPrefix(string ar[], int n)
{
  
    // If size is 0, return empty string
    if (n == 0)
        return "";
  
    if (n == 1)
        return ar[0];
  
    // Sort the given array
    sort(ar, ar + n);
  
    // Find the minimum length from 
    // first and last string
    int en = min(ar[0].size(), 
                 ar[n - 1].size());
  
    // Now the common prefix in first and 
    // last string is the longest common prefix
    string first = ar[0], last = ar[n - 1];
    int i = 0;
    while (i < en && first[i] == last[i])
        i++;
  
    string pre = first.substr(0, i);
    return pre;
}
  
// Driver Code
int main()
{
    string ar[] = {"geeksforgeeks", "geeks", 
                           "geek", "geezer"};
    int n = sizeof(ar) / sizeof(ar[0]);
    cout << "The longest common prefix is: "
         << longestCommonPrefix(ar, n);
    return 0;
}
  
// This code is contributed by jrolofmeister

Producción: 
 

The longest common prefix is : gee

Complejidad de tiempo: O (MAX * n * log n) donde n es el número de strings en la array y MAX es el número máximo de caracteres en cualquier string. Tenga en cuenta que la comparación de dos strings tomaría como máximo el tiempo O (MAX) y para ordenar n strings, necesitaríamos el tiempo O (MAX * n * log n).
Consulte el artículo completo sobre el prefijo común más largo usando la clasificación para obtener más detalles.