时间戳

首页 > 解决方案 > 在 Python 中查找与正则表达式匹配的所有（包括重叠的）子字符串

python - 在 Python 中查找与正则表达式匹配的所有（包括重叠的）子字符串

问题描述

我需要在字符串中找到与正则表达式匹配的所有子字符串的位置。例如，如果字符串是abbba并且正则表达式是(b|bb)(?=a)，则结果应该是[(2, 4), (3, 4)]。

我想出的是

def get_ranges(pattern: str, string: str) -> list[tuple[int, int]]:
    n = len(string)
    return [(start, end) for start in range(n + 1) for end in range(start, n + 1)
            if re.fullmatch(f'.{{{start}}}({pattern}).{{{n - end}}}', string)]

但这往往执行得非常缓慢，特别是考虑到它不允许使用预编译的正则表达式。有没有更有效的方法来解决问题？

标签： pythonregexperformance

解决方案

首先我认为你应该使用for end in range(start, n + 1). 对于end变量，我看不出有任何理由每次迭代都从 0 开始。只需进行此编辑，执行此代码

for i in range(300000):
    get_ranges(r"(b|bb)(?=a)", "abbba")

我从 9.67 秒到 6.01 秒。

推荐阅读