Регулярное выражение находит самый длинный общий префикс двух строк

Question

Существует ли регулярное выражение, которое бы находило самый длинный общий префикс из двух строк? И если это не может быть решено одним регулярным выражением, что будет самым элегантным фрагментом кода или однострочником, использующим регулярное выражение (perl, ruby, python, что угодно).

PS: я могу сделать это легко программно, я прошу скорее любопытства, потому что мне кажется, что это можно решить с помощью регулярного выражения.

PPS: дополнительный бонус за решение O (n) с использованием регулярных выражений. Да ладно, оно должно существовать!

Answer 1

Использование расширенных регулярных выражений, как в Foma или 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));

Самое сложное здесь - определить «самый длинный». Вообще говоря, чтобы оптимизировать, вы строите набор неоптимальных строк (ухудшение) и затем удалите их (фильтрация).

Это действительно пуристический подход, который позволяет избежать нерегулярных операций. такой захват.

Answer 2

Я второй ответ Руаха для регулярного выражения (с моей предложенной оптимизацией в комментариях). Простой в написании, но не простой и эффективный для запуска, если первая строка длинная.

Вот эффективный, не регулярное выражение, читаемый однострочный ответ:

$ 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 3

У меня есть идея, что это наиболее неэффективно. Нет ошибок и т. Д.

#!/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 4

Не регулярное выражение, не дублирующаяся строка в каждом итерационном решении:

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