Как реализовать алгоритм сопоставления регулярных выражений на основе NFA или DFA, чтобы найти все совпадения?

Question

Матчи могут быть перекрыты.

Но если найдено несколько совпадений, начиная с одной и той же позиции, выберите короткую.

Например, чтобы найти регулярное выражение parttern "a. * D" в строке "abcabdcd" , ответ должен быть { "abcabd" , "абд" }. И "abcabdcd" и "abdcd" не должны быть включены.

Answer 1

Большинство механизмов RE по умолчанию сопоставляют RE только один раз и с жадностью, и построенные вокруг них стандартные итерационные стратегии, как правило, возобновляют поиск после end предыдущего соответствия. Чтобы сделать что-то другое, требуется дополнительная хитрость. (Этот код 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]

Answer 2

Эта функция довольно неэффективна, но она решает вашу проблему:

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']

Диапазоны предполагают, что ваш шаблон содержит хотя бы один символ и не соответствует пустой строке. Кроме того, вам следует рассмотреть возможность использования ? для несжатого сопоставления шаблонов, чтобы повысить производительность и избежать внутреннего цикла.