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

Ответ 1

Если есть какой-то символ, который ни одна строка не содержит —, say, \0 — вы можете написать

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

и самый длинный общий префикс будет сохранен как $1.

Отредактировано для добавления: Это, очевидно, очень неэффективно. Я думаю, что если эффективность является проблемой, то это просто не тот подход, который мы должны использовать; но мы можем, по крайней мере, улучшить его, изменив .* на [^\0]*, чтобы предотвратить бесполезную жадность, которую нужно просто вернуть назад, и обернуть второй [^\0]* в (?>…), чтобы предотвратить обратное отслеживание, которое не может помочь. Это:

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

Это даст тот же результат, но гораздо эффективнее. (Но все же не так эффективно, как простой подход, основанный на использовании не регулярных выражений. Если строки имеют длину n, я ожидаю, что его худший случай займет не менее O (n ²), в то время как простой подход, основанный не на основе регулярных выражений, в наихудшем случае будет принимать O (n) время.)

Ответ 2

Здесь однострочный Python:

>>> a = 'stackoverflow'
>>> 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: ''
>>> 

Ответ 3

Здесь один довольно эффективный способ использования регулярного выражения. Код находится в Perl, но этот принцип должен быть адаптирован к другим языкам:

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

(Замечание, которое стоит отметить, заключается в том, что оператор XOR строки XOR (^) в действительности накладывает более короткую строку с нулями, чтобы она соответствовала длине более длинной. Таким образом, если строки могут содержать нулевые символы, а если короче строка является префиксом более длинной, общая длина префикса, рассчитанная с помощью этого кода, может превышать длину более короткой строки.)

Ответ 4

простой и эффективный

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

Ответ 5

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

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

Итак, в приведенном ниже примере я использую пробелы как разделитель

>>> 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'

Ответ 6

Здесь O (N) -решение с Foma-подобными регулярными выражениями псевдокода над тройками (для lcp у вас есть два входа и выход). Чтобы это было просто, я предполагаю двоичный алфавит {a, b}:

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

Теперь вам нужен только язык, который реализует многоленточные преобразователи.

Ответ 7

Другая попытка решения O (n):

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

зависит от того, считается ли. {n} O (1) или O (n), я не знаю, насколько эффективно это реализовано.

Примечания: 1.\0 не должно быть ни в одной строке, он используется как разделитель 2. результат в $_

Ответ 8

Вдохновленный ответ ruakh, вот решение регулярного выражения O (n):

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

Примечания:  1. ни одна строка не содержит \0  2. Самый длинный общий префикс будет сохранен как $1  3. пространство важно!

Изменить: Хорошо, что это не так правильно, как измерения rukach, но идея правильная, но мы должны нажать кнопку регулярного выражения, чтобы не проверять начальные буквы повторно. Основная идея может быть также переписана в этом perl oneliner.

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

Интересно, может ли он быть включен в regexp-решение.

Ответ 9

Может быть полезно в некоторых удаленных случаях, так что вот оно:

Решение только RegEx в 3 этапа (не удалось создать RegEx за один раз):

Строка A: abcdef
Строка B: abcxef

• 1-й проход: создайте RegEx из String A (часть 1):
  Матч: /(.)/g
  Заменить: \1(
  Результат: a(b(c(d(e(f(
  Объяснение демо: http://regex101.com/r/aJ4pY7

• 2-й прогон: создать RegEx из 1st pass result
  Матч: /^(.\()(?=(.*)$)|\G.\(/g
  Заменить: \1\2)?+
  Результат: a(b(c(d(e(f()?+)?+)?+)?+)?+)?+
  Объяснение демо: http://regex101.com/r/xJ7bK7

• Третий проход: test String B против RegEx, созданного в 2nd pass
  Матч: /a(b(c(d(e(f()?+)?+)?+)?+)?+)?+/
  Результат: abc (объясненная демонстрация)

И вот прославленный однострочный в PHP:

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

Код в режиме реального времени: http://codepad.viper-7.com/dCrqLa

Ответ 10

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

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

Ответ 11

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

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

$ 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

Ответ 12

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

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

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

Ответ 13

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

#!/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";