Regexp находит самый длинный общий префикс двух строк
Есть ли регулярное выражение, которое могло бы найти самый длинный общий префикс двух строк? И если это не разрешимо одним регулярным выражением, то какой будет самый элегантный фрагмент кода или oneliner с использованием regexp (perl, ruby, python, anything).
PS: Я могу сделать это легко программно, я задаю скорее любопытство, потому что мне кажется, что это можно решить с помощью regexp.
PPS: дополнительный бонус для решения O (n) с использованием регулярных выражений. Пойдем, он должен существовать!
Ответы
Ответ 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 2), в то время как простой подход, основанный не на основе регулярных выражений, в наихудшем случае будет принимать 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";