Wie implementieren Sie einen NFA- oder DFA -basierten Regexp -Matching -Algorithmus, um alle Übereinstimmungen zu finden?

Question

Die Übereinstimmungen können überlappt werden.

Wenn jedoch mehrere Übereinstimmungen aus derselben Position gefunden werden, wählen Sie die kurze Auswahl.

Zum Beispiel um Regexp Parttern zu finden "Anzeige" in einer Saite "ABCABDCD", die Antwort sollte {{sein"Abcabd", "Abd"}. Und "ABCABDCD" und "ABDCD" sollte nicht einbezogen werden.

Answer 1

Die meisten RE -Motoren stimmen standardmäßig nur einmal und gierig überein, und Standard -Iterationsstrategien, die um sie herum aufgebaut sind Ende des vorherigen Spiels. Anders als das zu tun, erfordert einige zusätzliche Tricks. (Dieser Code ist TCL, aber Sie sollten in vielen anderen Sprachen replizieren können.)

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

Diese Funktion ist ziemlich ineffizient, löst jedoch Ihr Problem:

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")

Ausgabe:

['abcabd', 'abd']

Die Bereiche gehen davon aus, dass Ihr Muster mindestens einen Zeichen enthält und nicht mit einer leeren Zeichenfolge übereinstimmt. Zusätzlich sollten Sie in Betracht ziehen, verwenden ? Damit Ihre Muster nicht vorbereitet sind, um die Leistung zu verbessern und die innere Schleife zu vermeiden.