Programa de Python para encontrar el prefijo común más largo usando 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.

longest_common_prefix

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

Python3

# Python3 Program to find the longest 
# common prefix
  
# A Utility Function to find the common 
# prefix between strings- str1 and str2
def commonPrefixUtil(str1, str2):
    result = "";
    n1 = len(str1)
    n2 = len(str2)
  
    # Compare str1 and str2
    i = 0
    j = 0
  
    while i <= n1 - 1 and j <= n2 - 1:    
        if (str1[i] != str2[j]):
            break
              
        result += str1[i]
        i += 1
        j += 1
  
    return (result)
  
# A Function that returns the longest 
# common prefix from the array of strings
def commonPrefix (arr, n):
    prefix = arr[0]
  
    for i in range (1, n):
        prefix = commonPrefixUtil(prefix, 
                                  arr[i])
    return (prefix)
  
# Driver Code
if __name__ =="__main__":
    arr = ["geeksforgeeks", "geeks",
           "geek", "geezer"]
    n = len(arr)
    ans = commonPrefix(arr, n)
  
    if (len(ans)):
        print ("The longest common prefix is -",
                ans);
    else:
        print("There is no common prefix")
  
# This code is contributed by ita_c

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!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *