Ordene una array de strings lexicográficamente según el prefijo

Dada una array de strings arr[] de tamaño N , la tarea es ordenar la array de strings en orden lexicográfico y si mientras se ordenan dos strings A y B , si la string A es el prefijo de la string B , entonces la string B debería aparecer en el orden ordenado.

Ejemplos:

Entrada: arr[] = {“sol”, “luna”, “simulacro”} 
Salida: 
simulacro 
luna 
sol 
Explicación: 
La clasificación lexicográfica es simulacro, luna y sol.

Entrada: arr[] = {“geeks”, “geeksfor”, “geeksforgeeks”} 
Salida: 
geeksforgeeks 
geeksfor 
geeks 
 

Enfoque: la idea es ordenar la array dada de strings usando la función de ordenación incorporada usando la función de comparación a continuación. La función de comparación utilizada para verificar si alguna string aparece como una substring en otra string usando la función de comparación() en C++ , luego debería organizarlos en orden decreciente de su longitud.

bool my_compare(string a, string b)
{
    // If any string is a substring then
    // return the size with greater length
    if (a.compare(0, b.size(), b) == 0
        || b.compare(0, a.size(), a) == 0)
        return a.size() & gt;
    b.size();
 
    // Else return lexicographically
    // smallest string
    else return a & lt;
    b;
}

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the vector
void Print(vector<string> v)
{
    for (auto i : v)
        cout << i << endl;
}
 
// Comparator function to sort the
// array of string wrt given conditions
bool my_compare(string a, string b)
{
    // Check if a string is present as
    // prefix in another string, then
    // compare the size of the string
    // and return the larger size
    if (a.compare(0, b.size(), b) == 0
        || b.compare(0, a.size(), a) == 0)
 
        return a.size() > b.size();
 
    // Else return lexicographically
    // smallest string
    else
        return a < b;
}
 
// Driver Code
int main()
{
    // GIven vector of strings
    vector<string> v = { "batman", "bat", "apple" };
 
    // Calling Sort STL with my_compare
    // function passed as third parameter
    sort(v.begin(), v.end(), my_compare);
 
    // Function call to print the vector
    Print(v);
    return 0;
}

apple
batman
bat

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)