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

Question

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

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

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

Answer 1

Если есть какой-либо символ, который не содержит ни одной строки & mdash ;, скажем, \0 & mdash; Вы могли бы написать

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

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

---

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

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

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

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

Answer 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 строки Perl (^) в действительности дополняет более короткую строку нулями досоответствует длине более длинного. Таким образом, если строки могут содержать нулевые символы, и , если более короткая строка является префиксом более длинной, длина общего префикса, рассчитанная с помощью этого кода, может превышатьдлина более короткой нити.)

Answer 4

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

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

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

Answer 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 (Σ:Σ:ε)*)

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

Answer 7

Еще одна попытка решения O (n):

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

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

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

Answer 8

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

Решение только для 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

• 3-й проход: тест 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

Answer 9

Вдохновленный ответом ruakh, вот решение O (n) regexp:

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

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

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

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

Интересно, можно ли ее снова включить в решение регулярных выражений.

Answer 10

Вот решение, которое я реализовал для проблемы с 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]

Надеюсь, это поможет