Regexp找到两个字符串的最长公共前缀

Question

是否有正则表达式可以找到两个字符串中最长的公共前缀？如果一个正则表达式无法解决这个问题,那么使用regexp(perl,ruby,python,any)的最优雅的代码或oneliner是什么.

PS:我可以通过编程轻松地做到这一点,我要求好奇心,因为在我看来这可以通过regexp解决.

PPS:使用正则表达式的O(n)解决方案的额外奖励.来吧,它应该存在!

Answer 1

如果某个字符不包含任何字符串 - 比如说\0- 你可以写

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

并且最长的公共前缀将保存为$1.

编辑补充:这显然效率很低.我认为如果效率是一个问题,那么这根本不是我们应该使用的方法; 但我们至少可以通过改变改进.*,以[^\0]*防止无用的贪念,将只需要再次回溯,和包装第二[^\0]*在(?>…)防止回溯不能帮助.这个:

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

这将产生相同的结果,但效率更高.(但仍然没有像直接的非正则表达式方法那样有效.如果字符串都具有长度n,我预计其最坏的情况至少需要O(n ²)时间,而直接的非正则表达式 -基础的方法将采取O(ñ的)时间的最坏的情况.)

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

(值得注意的是,Perl的字符串XOR运算符(^)实际上填充了带有空值的较短字符串以匹配较长字符串的长度.因此,如果字符串可能包含空字符,并且较短的字符串恰好是前缀对于较长的一个,使用此代码计算的公共前缀长度可能会超过较短字符串的长度.)

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'