正则表达式查找两个字符串的最长公共前缀 [英] Regexp finding longest common prefix of two strings

问题描述

是否存在一个正则表达式，可以找到两个字符串的最长公共前缀?而且如果一个正则表达式无法解决这个问题，那么使用正则表达式(perl，ruby，python，其他任何东西)最优雅的代码或oneliner就是什么.

Is there a regexp which would find longest common prefix of two strings? And if this is not solvable by one regexp, what would be the most elegant piece of code or oneliner using regexp (perl, ruby, python, anything).

PS:我可以通过编程轻松地做到这一点，我只是出于好奇心，因为在我看来这可以通过正则表达式解决.

PS: I can do this easily programatically, I am asking rather for curiosity, because it seems to me that this could be solveable by regexp.

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

PPS: Extra bonus for O(n) solution using regexps. Come on, it should exist!

推荐答案

如果有些字符两个字符串都不包含&mdash ;，例如\0—你可以写

If there's some character that neither string contains —, say, \0 — you could write

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

，最长的公共前缀将另存为$1.

and the longest common prefix would be saved as $1.

编辑后添加:这显然效率很低.我认为，如果要关注效率，那么这根本不是我们应该使用的方法.但我们至少可以通过将.*更改为[^\0]*来防止不必要的贪婪而将其再次回溯，并将第二个[^\0]*包裹在(?>…)中以防止回溯无济于事，从而改善它.这个:

Edited to add: This is obviously very inefficient. I think that if efficiency is a concern, then this simply isn't the approach we should be using; but we can at least improve it by changing .* to [^\0]* to prevent useless greediness that will just have to be backtracked again, and wrapping the second [^\0]* in (?>…) to prevent backtracking that can't help. This:

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

这将产生相同的结果，但效率更高. (但仍然不能像基于正则表达式的直接方法一样有效地实现 .如果两个字符串的长度都为 n ，我希望它的最坏情况至少会花费O( n ² )时间，而简单的基于非正则表达式的方法将花费O( n )时间< n 最坏的情况.)

This will yield the same result, but much more efficiently. (But still not nearly as efficiently as a straightforward non–regex-based approach. If the strings both have length n, I'd expect its worst case to take at least O(n²) time, whereas the straightforward non–regex-based approach would take O(n) time in its worst case.)

这篇关于正则表达式查找两个字符串的最长公共前缀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！