Determine el prefijo de un conjunto de cadenas (similares)

Tengo un conjunto de cadenas, por ejemplo,

my_prefix_what_ever my_prefix_what_so_ever my_prefix_doesnt_matter 

Simplemente quiero encontrar la porción común más larga de estas cadenas, aquí el prefijo. En lo anterior el resultado debe ser

 my_prefix_ 

Las cuerdas

 my_prefix_what_ever my_prefix_what_so_ever my_doesnt_matter 

debe resultar en el prefijo

 my_ 

¿Existe una forma relativamente indolora en Python para determinar el prefijo (sin tener que repetir manualmente cada carácter)?

    PD: estoy usando Python 2.6.3.

    Nunca reescribas lo que se te proporciona: os.path.commonprefix hace exactamente esto:

    Devuelve el prefijo de ruta más largo (tomado carácter por carácter) que es un prefijo de todas las rutas en la lista. Si la lista está vacía, devuelva la cadena vacía ( '' ). Tenga en cuenta que esto puede devolver rutas no válidas porque funciona un carácter a la vez.

    Para comparar con las otras respuestas, aquí está el código:

     # Return the longest prefix of all list elements. def commonprefix(m): "Given a list of pathnames, returns the longest common leading component" if not m: return '' s1 = min(m) s2 = max(m) for i, c in enumerate(s1): if c != s2[i]: return s1[:i] return s1 

    Ned Batchelder probablemente tenga razón. Pero por el gusto de hacerlo, aquí hay una versión más eficiente de la respuesta de itertools usando itertools .

     import itertools strings = ['my_prefix_what_ever', 'my_prefix_what_so_ever', 'my_prefix_doesnt_matter'] def all_same(x): return all(x[0] == y for y in x) char_tuples = itertools.izip(*strings) prefix_tuples = itertools.takewhile(all_same, char_tuples) ''.join(x[0] for x in prefix_tuples) 

    Como una afrenta a la legibilidad, aquí hay una versión de una línea 🙂

     >>> from itertools import takewhile, izip >>> ''.join(c[0] for c in takewhile(lambda x: all(x[0] == y for y in x), izip(*strings))) 'my_prefix_' 

    Aquí está mi solución:

     a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"] prefix_len = len(a[0]) for x in a[1 : ]: prefix_len = min(prefix_len, len(x)) while not x.startswith(a[0][ : prefix_len]): prefix_len -= 1 prefix = a[0][ : prefix_len] 

    La siguiente es una solución operativa, pero probablemente bastante ineficiente.

     a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"] b = zip(*a) c = [x[0] for x in b if x==(x[0],)*len(x)] result = "".join(c) 

    Para pequeños conjuntos de cadenas, lo anterior no es un problema en absoluto. Pero para conjuntos más grandes, personalmente codificaría otra solución manual que verifica cada carácter uno tras otro y se detiene cuando hay diferencias.

    Algorítmicamente, esto produce el mismo procedimiento, sin embargo, uno podría evitar construir la lista c .

    Solo por curiosidad descubrí otra manera de hacer esto:

     def common_prefix(strings): if len(strings) == 1:#rule out trivial case return strings[0] prefix = strings[0] for string in strings[1:]: while string[:len(prefix)] != prefix and prefix: prefix = prefix[:len(prefix)-1] if not prefix: break return prefix strings = ["my_prefix_what_ever","my_prefix_what_so_ever","my_prefix_doesnt_matter"] print common_prefix(strings) #Prints "my_prefix_" 

    Como señaló Ned, probablemente sea mejor usar os.path.commonprefix , que es una función bastante elegante.

    La segunda línea de este emplea la función de reducción en cada carácter en las cadenas de entrada. Devuelve una lista de N + 1 elementos donde N es la longitud de la cadena de entrada más corta.

    Cada elemento del lote es (a) el carácter de entrada, si todas las cadenas de entrada coinciden en esa posición, o (b) Ninguna. lot.index (Ninguno) es la posición del primer Ninguno en el lote: la longitud del prefijo común. fuera es ese prefijo común.

     val = ["axc", "abc", "abc"] lot = [reduce(lambda a, b: a if a == b else None, x) for x in zip(*val)] + [None] out = val[0][:lot.index(None)] 

    Aquí hay otra forma de hacerlo usando OrderedDict con un código mínimo.

     import collections import itertools def commonprefix(instrings): """ Common prefix of a list of input strings using OrderedDict """ d = collections.OrderedDict() for instring in instrings: for idx,char in enumerate(instring): # Make sure index is added into key d[(char, idx)] = d.get((char,idx), 0) + 1 # Return prefix of keys while value == length(instrings) return ''.join([k[0] for k in itertools.takewhile(lambda x: d[x] == len(instrings), d)]) 

    Aquí hay una solución simple y limpia. La idea es usar la función zip () para alinear a todos los caracteres colocándolos en una lista de los primeros caracteres, la lista de los segundos personajes, … la lista de los caracteres nth. Luego itere cada lista para verificar si contienen solo 1 valor.

     a = ["my_prefix_what_ever", "my_prefix_what_so_ever", "my_prefix_doesnt_matter"] list = [all(x[i] == x[i+1] for i in range(len(x)-1)) for x in zip(*a)] print a[0][:list.index(0) if list.count(0) > 0 else len(list)] 

    salida: mi_prefijo_