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

Question

是否有一个regexp可以找到两个字符串的最长公共前缀？如果一个regexp不能解决这个问题，那么使用regexp（perl、ruby、python等）的最优雅的代码或oneliner是什么呢。

PS:我可以很容易地用编程的方式来完成这项工作，我是出于好奇，因为在我看来，regexp可以解决这个问题。

PPS：使用regexps的O（n）解决方案的额外奖励。快点，它应该存在！

Answer 1

下面是一条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 2

如果两个字符串都不包含某个字符，比如\0-您可以编写

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

最长的公共前缀将保存为$1。

---

编辑后添加：这显然效率很低。我认为，如果效率是一个问题，那么这根本不是我们应该使用的方法；但我们至少可以通过将.*更改为[^\0]*来改进它，以防止无用的贪婪，而这种贪婪将不得不再次被回溯，并将第二个[^\0]*包装在(?>…)中，以防止无法帮助的回溯。这：

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

这将产生相同的结果，但效率更高。（但仍然不如直接的基于非正则表达式的方法有效。如果两个字符串都有长度n，我预计最坏的情况至少需要O（n²）时间，而直接的基于非正则表达式的方法在its最坏的情况下需要O（n）时间。）

Answer 3

这里有一个相当有效的方法使用regexp。代码是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的string XOR操作符（^）实际上用空填充较短的字符串，以匹配较长字符串的长度。因此，如果字符串可能包含空字符，和如果短字符串恰好是长字符串的前缀，则使用此代码计算的公共前缀长度可能超过短字符串的长度。）