4

匹配可以重叠。

但是，如果从同一位置开始找到多个匹配项，则选择较短的一个。

例如，要在字符串"abcabdcd"中查找正则表达式部分"a.*d"，答案应该是 { "abcabd" , "abd" }。并且不应包含“abcabdcd”和“abdcd” 。

4

2 回答 2

0

此功能效率相当低，但它解决了您的问题：

def find_shortest_overlapping_matches(pattern, line):
        pat=re.compile(pattern)
        n=len(line)
        ret=[]
        for start in xrange(0, n):
                for end in xrange(start+1, n+1):
                        tmp=line[start:end]
                        mat=pat.match(tmp)
                        if mat is not None:
                                ret.append(tmp)
                                break
        return ret

print find_shortest_overlapping_matches("a.*d", "abcabdcd")

输出：

['abcabd', 'abd']

范围假定您的模式至少包含一个字符并且不匹配空字符串。此外，您应该考虑使用?使您的模式以非贪婪方式匹配以提高性能并避免内部循环。

于 2012-02-20T09:27:50.430 回答
0

大多数 RE 引擎默认只匹配一次 RE，并且是贪婪的，围绕它们构建的标准迭代策略往往会在上一次匹配结束后重新开始搜索。除此之外，还需要一些额外的技巧。（此代码是 Tcl，但您应该能够以许多其他语言复制它。）

proc matchAllOverlapping {RE string} {
    set matches {}
    set nonGreedyRE "(?:${RE}){1,1}?"
    set idx 0
    while {[regexp -indices -start $idx $nonGreedyRE $string matchRange]} {
        lappend matches [string range $string {*}$matchRange]
        set idx [expr { [lindex $matchRange 0] + 1 }]
    }
    return $matches
}
puts [matchAllOverlapping a.*d abcabdcd]
于 2012-02-20T09:47:11.207 回答