正则表达式查找两个字符串的最长公共前缀

Question

有没有一种正则表达式可以找到两个字符串的最长公共前缀？如果不能用一个正则表达式解决，那用正则表达式写出最优雅的代码或一行代码（可以是perl、ruby、python等语言）会是什么样的呢？

附注：我其实可以很简单地用程序来做到这一点，我只是出于好奇在问，因为我觉得用正则表达式也许能解决这个问题。

附加说明：如果能用正则表达式找到O(n)的解决方案，那就更棒了！我觉得应该有这样的解决办法！

Answer 1

这里有一种相对高效的方法，它使用了正则表达式。代码是用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的字符串异或运算符（^）实际上会用空字符填充较短的字符串，以匹配较长字符串的长度。因此，如果字符串中可能包含空字符，并且较短的字符串恰好是较长字符串的前缀，那么用这段代码计算出的公共前缀长度可能会超过较短字符串的长度。

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

如果有一个字符在两个字符串中都没有，比如说 \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) 的时间。）