Programa Java para encontrar el prefijo común más largo utilizando 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:

// Java Program to find the longest 
// common prefix 
class GFG {
  
// A Utility Function to find the common 
// prefix between strings- str1 and str2 
static 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.charAt(i) != str2.charAt(j)) 
        {
            break;
        }
            result += str1.charAt(i);
    }
        return (result);
}
  
// A Function that returns the longest 
// common prefix from the array of strings 
static 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
public static void main(String[] args) 
{
    String arr[] = {"geeksforgeeks", "geeks",
                    "geek", "geezer"};
    int n = arr.length;
    String ans = commonPrefix(arr, n);
  
    if (ans.length() > 0) 
    {
        System.out.printf("The longest common prefix is - %s",
                           ans);
    } 
    else 
    {
        System.out.printf("There is no common prefix");
    }
}
}
// This code is contributed by 29AjayKumar

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!