使用 Python 3 和动态规划找到所有重叠模式无限循环

Question

我在看： Python regex find all overlapping matches? 和 re.finditer 对我不起作用。我不想下载另一个模块（即 regex）来替换内置的 re。我以为我可以自己写，但我对 while loops 的理解是有限的。

我正在尝试制作一个搜索包装器，即使它们重叠也能找到所有模式（当前 findall 在 re 中没有做的一件事）。

我也从来没有尝试过编写这样的程序，所以我不想为此使用内置模块，而是想尝试构建自己的函数，这样我就可以学习如何动态编程。

def findall_positions(pattern, sequence):
    positions = list()
    cont = True

    while cont == True:
        match = re.search(pattern, sequence)
        if match is not None:
            positions.append(match.start())
            sequence = sequence[positions[-1]:]
        if match is None:
            cont = False
    return positions

findall_positions("AB","ABBABBABBBA")

我的逻辑是 re.search，如果命中，将开始附加到 positions，然后在第一个 re.search match 之后获取字符串的下一段并遍历直到 match is None。但是，我遇到了无限循环。 我如何重组它以获得正确的结果？ 我正在寻找 [0,3,6]

的输出

Answer 1

上述方法的问题是第一个匹配的开始是在偏移 0 处，因此在第一次迭代中 positions 是 [0]。然后 sequence = sequence[positions[-1]:] 自然会生成原始字符串，因此你有无限循环。

您可以有一个单独的变量来跟踪偏移量并在每次执行时构造新字符串 re.search。如果找到匹配项，则相应地调整位置：

import re

def findall_positions(pattern, sequence):
    positions = list()
    cont = True
    offset = 0

    while cont == True:
        match = re.search(pattern, sequence[offset:])
        if match is not None:
            positions.append(match.start() + offset)
            offset = positions[-1] + 1
        if match is None:
            cont = False
    return positions

print(findall_positions("AB","ABBABBABBBA"))

输出：

[0, 3, 6]

使用 Python 3 和动态规划找到所有重叠模式无限循环

Find all overlapping patterns infinite loop, using Python 3 and dynamic programming

python

regex

search

position

findall