如何使用正则表达式找到最短的重叠匹配？

18 投票

9 回答

8584 浏览

提问于 2025-04-15 18:33

我对正则表达式还比较陌生。现在我想找到一段文本中最短的字符串，这个字符串要符合特定的模式，但如果最短的模式是一个更大匹配的子串，我就遇到麻烦了。举个例子：

import re
string = "A|B|A|B|C|D|E|F|G"
my_pattern = 'a.*?b.*?c'

my_regex = re.compile(my_pattern, re.DOTALL|re.IGNORECASE)
matches = my_regex.findall(string)

for match in matches:
    print match

打印结果是：

A|B|A|B|C

但我希望它能返回：

A|B|C

有没有办法做到这一点，而不需要逐个检查每个匹配项，看看它是否包含一个符合条件的子串呢？

正则表达式字符串匹配模式识别重叠匹配子串查找

9 个回答

这可能是一个有用的应用，叫做 sexegers。正则表达式匹配通常会优先选择最长的、最左边的选项。使用像 .*? 这样的非贪婪量词可以避免选择最长的部分，而反转输入和模式可以绕过最左匹配的规则。

考虑下面这个程序，它可以输出 A|B|C，正是我们想要的结果：

#! /usr/bin/env python

import re

string = "A|B|A|B|C|D|E|F|G"
my_pattern = 'c.*?b.*?a'

my_regex = re.compile(my_pattern, re.DOTALL|re.IGNORECASE)
matches = my_regex.findall(string[::-1])

for match in matches:
    print match[::-1]

另一种方法是制定一个更严格的模式。比如说，你不想允许已经出现过的字符重复：

my_pattern = 'a[^a]*?b[^ab]*?c'

你的例子比较通用且有点牵强，但如果我们能更清楚你正在处理的输入，我们就能提供更好、更有帮助的建议。

回答于 2025-04-15 由 Python大师

分享举报

不，Perl会返回最长的、最左边的匹配结果，同时也会遵循你设置的非贪婪量词。你可能需要使用循环来实现这个功能，抱歉。

补充：是的，我知道我上面提到了Perl，但我相信Python也是这样。

回答于 2025-04-15 由 Python大师

分享举报

与这里大多数其他回答不同，这个问题可以用一个正则表达式来解决，使用了一个叫做正向前瞻断言的技巧，还有一个捕获组：

>>> my_pattern = '(?=(a.*?b.*?c))'
>>> my_regex = re.compile(my_pattern, re.DOTALL|re.IGNORECASE)
>>> matches = my_regex.findall(string)
>>> print min(matches, key=len)
A|B|C

findall()这个函数会返回所有可能的匹配结果，所以你需要用min()来找到最短的那个。

这个方法是怎么工作的：

在这个正则表达式中，我们并不是在匹配具体的文本，而是在匹配字符串中的位置（正则引擎在尝试匹配时会逐个检查这些位置）。
在每个位置，正则引擎会向前看，看看你的正则表达式在这个位置是否能匹配。
如果能匹配，它就会被捕获组记录下来。
如果不能匹配，就不会被记录。
无论结果如何，正则引擎都会向前移动一个字符，然后重复这个过程，直到字符串的末尾。
因为前瞻断言不会消耗任何字符，所以所有重叠的匹配都会被找到。

回答于 2025-04-15 由 Python大师

分享举报

如何使用正则表达式找到最短的重叠匹配？

9 个回答

撰写回答