查找两个字符串之间的最短匹配

问题描述：

我有一个很大的日志文件，我想提取两个字符串之间的多行字符串：start和end。

以下是来自 的示例inputfile：

start spam
start rubbish
start wait for it...
    profit!
here end
start garbage
start second match
win. end

所需的解决方案应该打印：

start wait for it...
    profit!
here end
start second match
win. end

我尝试了一个简单的正则表达式，但它返回了所有内容start spam。应该怎么做？

编辑：有关实际计算复杂性的附加信息：

• 实际文件大小：2GB

• ‘start’ 的出现次数：~ 12 M，均匀分布

• ‘end’ 出现次数：~800，靠近文件末尾。

解决方案 1：

这个正则表达式应该符合你的要求：

(start((?!start).)*?end)

使用re.findall方法和单行修饰符re.S来获取多行字符串中的所有出现次数：

re.findall('(start((?!start).)*?end)', text, re.S)

在此处查看测试。

解决方案 2：

用代码来实现——基本状态机：

open = False
tmp = []
for ln in fi:
    if 'start' in ln:
        if open:
            tmp = []
        else:
            open = True

    if open:
        tmp.append(ln)

    if 'end' in ln:
        open = False
        for x in tmp:
            print x
        tmp = []

解决方案 3：

这很难做到，因为默认情况下，re模块不会查看重叠匹配。较新版本的 Python 有一个regex允许重叠匹配的新模块。

https://pypi.python.org/pypi/regex

你可能想使用类似

regex.findall(pattern, string, overlapped=True)

如果你被困在 Python 2.x 或其他没有的版本中regex，那么使用一些技巧仍然可行。一位聪明的人在这里解决了这个问题：

Python 正则表达式找到所有重叠匹配吗？

一旦你有了所有可能重叠的（我想是非贪婪的）匹配，只需确定哪一个最短，这应该很容易。

解决方案 4：

您可以这样做(?s)start.*?(?=end|start)(?:end)?，然后过滤掉所有不以“end”结尾的事物。