examples - python split regex

Regexp encuentra el prefijo común más largo de dos cadenas

Question

¿Hay una expresión regular que encontraría el prefijo común más largo de dos cadenas? Y si esto no se puede resolver con una expresión regular, ¿cuál sería la pieza más elegante de código o delineador de líneas usando expresiones regulares (perl, ruby, python, cualquier cosa)?

PD: Puedo hacer esto fácilmente mediante programación, pido más bien curiosidad, porque me parece que esto podría resolverse mediante expresiones regulares.

PPS: bonificación extra para la solución O (n) utilizando expresiones regulares. Vamos, debería existir!

Answer 1

Aquí hay un One-Liner de Python:

>>> a = ''''
>>> b = ''stackofpancakes''
>>> a[:[x[0]==x[1] for x in zip(a,b)].index(0)]
0: ''stacko''
>>> a = ''nothing in''
>>> b = ''common''
>>> a[:[x[0]==x[1] for x in zip(a,b)].index(0)]
1: ''''
>>>

Answer 2

Aquí hay una forma bastante eficiente que usa una expresión regular. El código está en Perl, pero el principio debería ser adaptable a otros idiomas:

my $xor = "$first" ^ "$second"; # quotes force string xor even for numbers
$xor =~ /^/0*/; # match leading null characters
my $common_prefix_length = $+[0]; # get length of match

(Una sutileza que vale la pena señalar es que el operador XOR de cadena de Perl ( ^ ) en efecto almohadilla la cadena más corta con nulos para que coincida con la longitud de la más larga. Por lo tanto, si las cadenas pueden contener caracteres nulos, y si la cadena más corta pasa a ser una prefijo del más largo, la longitud del prefijo común calculada con este código podría exceder la longitud de la cadena más corta.)

Answer 3

Aquí hay una solución O (N) con expresiones regulares de pseudocódigo tipo Foma sobre triples (para lcp, tiene dos entradas y una salida). Para hacerlo simple, supongo que es un alfabeto binario {a, b}:

def match {a:a:a, b:b:b};
def mismatch {a:b:ε, b:a:ε};
def lcp match* ∪ (match* mismatch (Σ:Σ:ε)*)

Ahora solo necesita un lenguaje que implemente transductores de cintas múltiples.

Answer 4

Aquí hay una solución que implementé para un problema de leetcode:

def max_len(strs):
"""
:type strs: List[str]
:rtype: int
"""
min_s = len(strs[0]);
for s in strs:
if (len(s) < min_s):
min_s = len(s);
return min_s;
class Solution2:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
acc = -1;
test_len = max_len(strs);
for i in range(test_len):
t = strs[0][i];
acc2 = 0;
for j in range(len(strs)):
if (strs[j][i] == t):
acc2 += 1;
if (acc2 == len(strs)):
acc += 1;
if (acc == -1):
return ""
else:
return strs[0][:acc + 1]

Espero que esto ayude

Answer 5

Cadena no regexp, sin duplicación en cada solución de iteración:

def common_prefix(a, b):
#sort strings so that we loop on the shorter one
a, b = sorted((a,b), key=len)
for index, letter in a:
if letter != b[index]:
return a[:index - 1]
return a

Answer 6

El problema que tendrá es que una expresión regular coincide con una cadena a la vez, por lo que no está destinada a comparar dos cadenas.

Si hay un personaje del que puede estar seguro de que no está en ninguna de las cadenas, puede usarlo para separarlas en una sola cadena y luego buscar utilizando referencias anteriores para grupos.

Entonces en el siguiente ejemplo estoy usando espacios en blanco como el separador

>>> import re
>>> pattern = re.compile("(?P<prefix>/S*)/S*/s+(?P=prefix)")
>>> pattern.match("stack stable").group(''prefix'')
''sta''
>>> pattern.match("123456 12345").group(''prefix'')
''12345''

Answer 7

Inspirado por la respuesta de ruakh, aquí está la solución O (n) de expresiones regulares:

"$first /0$second" =~ m/^(.*?)(.).*/0/1(?!/2)/s;

Notas: 1. ninguna cadena contiene / 0 2. el prefijo común más largo se guardaría como $ 1 3. ¡el espacio es importante!

Edit: bueno, no es correcto como rukach, pero la idea es correcta, pero deberíamos presionar la máquina de expresiones regulares para que no verifique las letras de inicio repetidamente. La idea básica también puede ser reescrita en este perl oneliner.

perl -e '' $_="$first/0$second/n"; while(s/^(.)(.*?)/0/1//2/0/gs) {print $1;}; ''

Me pregunto si se puede incorporar de nuevo a la solución de expresiones regulares.

Answer 8

Otro intento de solución O (n):

$x=length($first); $_="$first/0$second"; s/((.)(?!.{$x}/2)).*//s;

depende de si. {n} se considera O (1) u O (n), no sé cuán eficientemente se implementa esto.

Notas: 1. / 0 no debe estar en ninguna de las cadenas, se usa como delimitador 2. el resultado está en $ _

Answer 9

Podría ser útil en algunos casos remotos , así que aquí va:

Solo solución RegEx en 3 pasos ( no se pudo crear un RegEx de una vez ):

Cadena A: abcdef
Cadena B: abcxef

• 1er paso: crear RegEx desde la String A (parte 1) :
  Coincidencia: /(.)/g
  Reemplazar: /1(
  Resultado: a(b(c(d(e(f(
  Explicación de demostración: http://regex101.com/r/aJ4pY7

• 2º paso: crear RegEx desde el 1st pass result del 1st pass result
  Coincidencia: /^(./()(?=(.*)$)|/G./(/g
  Reemplazar: /1/2)?+
  Resultado: a(b(c(d(e(f()?+)?+)?+)?+)?+)?+
  Explicación de demostración: http://regex101.com/r/xJ7bK7

• 3.er pase: prueba la String B contra el RegEx creado en el 2nd pass
  Coincidencia: /a(b(c(d(e(f()?+)?+)?+)?+)?+)?+/
  Resultado: abc ( demostración explicada )

Y aquí está el unísono glorificado en PHP:

preg_match(''/^''.preg_replace(''/^(./()(?=(.*)$)|/G./(/'',''/1/2)?+'',preg_replace(''/(.)/'',''/1('',$a)).''/'',$b,$longest);

Código en vivo en: http://codepad.viper-7.com/dCrqLa

Answer 10

Respuse la respuesta de ruakh para la expresión regular (con mi optimización sugerida en los comentarios). Simple de escribir, pero no simple y eficiente de ejecutar si la primera cadena es larga.

Aquí hay una respuesta eficiente, no regexp, legible, de una sola línea:

$ perl -E ''($n,$l)=(0,length $ARGV[0]); while ($n < $l) { $s = substr($ARGV[0], $n, 1); last if $s ne substr($ARGV[1], $n, 1); $n++ } say substr($ARGV[0], 0, $n)'' abce abcdef
abc

Answer 11

Tengo la idea de que esto es más ineficiente. No errar, etc.

#!/usr/bin/perl
use strict;
use warnings;
my($s1,$s2)=(@ARGV);
#find the shortest string put it into s1, if you will.
my $n=0;
my $reg;
foreach my $c (split(//,$s1)) { $reg .="($c"; $n++;}
$reg .= ")?" x $n;
$s2 =~ /$reg/;
print $&,"/n";

Answer 12

Usando expresiones regulares extendidas como en Foma o Xfst.

def range(x) x.l;
def longest(L) L - range(range(L ∘ [[Σ:ε]+ [Σ:a]*]) ∘ [a:Σ]*);
def prefix(W) range(W ∘ [Σ* Σ*:ε]);
def lcp(A,B) longest(prefix(A) ∩ prefix(B));

La parte más difícil aquí es definir "más larga". En términos generales, para optimizar, construyes el conjunto de cadenas no óptimas (empeoramiento) y luego las eliminas (filtrando).

Este es realmente un enfoque purista, que evita operaciones no regulares como la captura.

Answer 13

simple y eficiente

def common_prefix(a,b):
i = 0
for i, (x, y) in enumerate(zip(a,b)):
if x!=y: break
return a[:i]

Answer 14

Si hay algún personaje que ninguna cadena contiene, por ejemplo, /0 , podrías escribir

"$first/0$second" =~ m/^(.*).*/0/1/s;

y el prefijo común más largo se guardaría en $1 .

Editado para agregar: Esto es obviamente muy ineficiente. Creo que si la eficiencia es una preocupación, entonces simplemente este no es el enfoque que deberíamos usar; pero al menos podemos mejorarlo cambiando .* a [^/0]* para evitar la avaricia inútil que solo tendrá que retroceder de nuevo, y envolviendo el segundo [^/0]* en (?>…) para evitar retrocesos eso no puede ayudar. Esta:

"$first/0$second" =~ m/^([^/0]*)(?>[^/0]*)/0/1/s;

Esto arrojará el mismo resultado, pero mucho más eficiente. (Pero aún así no es tan eficiente como un enfoque directo no basado en expresiones regex. Si las cadenas tienen longitud n , esperaría que su peor caso tomara al menos O ( n ² ) tiempo, mientras que el directo no regex- el enfoque basado tomaría O ( n ) el tiempo en su peor caso).