Angenommen, Sie haben eine Zeichenfolge (z. B. needle ). Seine 19 kontinuierlichen Teilstrings sind:
Wenn ich eine Regex erstellen würde, die im Heuhaufen passt, könnte ich einfach irgendeinen der Teilstrings tun:
%Vor%aber es sieht nicht wirklich elegant aus. Gibt es eine bessere Möglichkeit, eine Regex zu erstellen, die gierig mit einem der Teilstrings einer gegebenen Zeichenfolge übereinstimmt?
Zusätzlich, was, wenn ich eine andere Einschränkung stellte, wollte nur Teilstrings passen, die länger als ein Schwellenwert sind, z.B. für Teilstrings von mindestens 3 Zeichen:
%Vor%Hinweis: Ich habe bewusst keinen bestimmten Regex-Dialekt erwähnt. Bitte geben Sie an, welche Sie in Ihrer Antwort verwenden.
Wie von Qtax vorgeschlagen, der Ausdruck
n(e(e(d(l(e)?)?)?)?)?|e(e(d(l(e)?)?)?)?|e(d(l(e)?)?)?|d(l(e)?)?|l(e)?|e
wäre der Weg zu gehen, wenn Sie einen expliziten regulären Ausdruck schreiben möchten ( egrep Syntax, optional ersetzen Sie (...) durch (?:...) ). Der Grund, warum dies besser als die anfängliche Lösung ist, ist, dass die komprimierte Version nur O (n ^ 2) Speicherplatz im Vergleich zu O (n ^ 3) Leerzeichen in der ursprünglichen Version benötigt, wobei n die Länge der Eingabe ist. Versuchen Sie dies mit extraordinarily als Eingabe, um den Unterschied zu sehen. Ich denke, die komprimierte Version ist auch schneller mit vielen Regexp-Engines da draußen.
Der Ausdruck
nee(d(l(e)?)?)?|eed(l(e)?)?|edl(e)?|dle
sucht nach Teilzeichenfolgen der Länge 3 oder länger.
Wie von vhallac hervorgehoben, sind die erzeugten regulären Ausdrücke ein wenig redundant und können optimiert werden. Neben dem vorgeschlagenen Emacs-Tool gibt es ein Perl-Paket Regexp :: Optimizer < Ich hoffe, dass es hier helfen würde, aber eine schnelle Überprüfung fehlgeschlagen für den ersten regulären Ausdruck.
Beachten Sie, dass viele Regexp-Engines standardmäßig eine nicht überlappende Suche durchführen. Überprüfen Sie dies mit den Anforderungen Ihres Problems.
Ich habe eine elegante Lösung gefunden, je nachdem, wie schlecht Sie nur eine Regexp brauchen. Zum Beispiel ist hier die Regexp, die gemeinsame Teilzeichenfolge (Perl) der Länge 7 findet:
%Vor%Die passende Zeichenfolge befindet sich in \ 1 . Zeichenfolgen sollten kein Nullzeichen enthalten, das als Trennzeichen verwendet wird.
Sie sollten einen Zyklus machen, der mit der Länge der Nadel beginnt und bis zum Grenzwert schwingt und versucht, die Regexp anzupassen.