Programa C++ para encontrar el prefijo común más largo usando la coincidencia palabra por palabra

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"

Empezamos con un ejemplo. Supongamos que hay dos strings: «geeksforgeeks» y «geeks». ¿Cuál es el prefijo común más largo en ambos? Es «frikis».
Ahora introduzcamos otra palabra «geek». Entonces, ¿cuál es el prefijo común más largo en estas tres palabras? Es «geek»
. Podemos ver que el prefijo común más largo tiene la propiedad asociativa, es decir,

LCP(string1, string2, string3) 
         = LCP (LCP (string1, string2), string3)

Like here

LCP (“geeksforgeeks”, “geeks”, “geek”)
     =  LCP (LCP (“geeksforgeeks”, “geeks”), “geek”)
     =  LCP (“geeks”, “geek”) = “geek”

Entonces podemos hacer uso de la propiedad asociativa anterior para encontrar el LCP de las strings dadas. Calculamos uno por uno el LCP de cada una de las strings dadas con el LCP hasta ahora. El resultado final será nuestro prefijo común más largo de todas las strings.
Tenga en cuenta que es posible que las strings dadas no tengan un prefijo común. Esto sucede cuando el primer carácter de todas las strings no es el mismo.
Mostramos el algoritmo con las strings de entrada: «geeksforgeeks», «geeks», «geek», «geezer» en la siguiente figura.

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

//  A C++ Program to find the longest 
// common prefix
#include<bits/stdc++.h>
using namespace std;
  
// A Utility Function to find the common 
// prefix between strings- str1 and str2
string commonPrefixUtil(string str1, 
                        string str2)
{
    string result;
    int n1 = str1.length(), 
        n2 = str2.length();
  
    // Compare str1 and str2
    for (int i = 0, j = 0; i <= n1 - 1 &&
             j <= n2 - 1; i++, j++)
    {
        if (str1[i] != str2[j])
            break;
        result.push_back(str1[i]);
    }
  
    return (result);
}
  
// A Function that returns the longest 
// common prefix from the array of strings
string commonPrefix (string arr[], int n)
{
    string prefix =  arr[0];
  
    for (int i = 1; i <= n - 1; i++)
        prefix = commonPrefixUtil(prefix, 
                                  arr[i]);
    return (prefix);
}
  
// Driver code
int main()
{
    string arr[] = {"geeksforgeeks", "geeks",
                    "geek", "geezer"};
    int n = sizeof(arr) / sizeof(arr[0]);
    string ans = commonPrefix(arr, n);
  
    if (ans.length())
        printf ("The longest common prefix is - %s",
                 ans.c_str());
    else
        printf("There is no common prefix");
  
    return (0);
}

Producción :

The longest common prefix is - gee

Complejidad de tiempo: dado que estamos iterando a través de todas las strings y para cada string estamos iterando a través de cada carácter, podemos decir que la complejidad de tiempo es O (NM) donde, 

N = Number of strings
M = Length of the largest string string 

Espacio auxiliar: para almacenar la string de prefijos más larga, estamos asignando un espacio que es O (M).
¡ Consulte el artículo completo sobre el prefijo común más largo usando la coincidencia palabra por palabra para obtener más detalles!