ein RE gegeben, leiten den größten Teilzeichen Spiel

Question

ich mich für ein Stück Code suchen, der wird:

Given regular expression E, derive the longest string X 
such that for every S, X is a substring of S iff S will match E 

Beispiele:

E = "a", X = "a" 
E = "^a$", X = "a" 
E = "a(b|c)", X = "a" 
E = "[ab]", X = "" 

Kontext: Ich möchte gegen einige reguläre Ausdrücke passen Ein Datenspeicher , der nur Teilstringsuche unterstützt. Es wäre nett , die Regular Expression-Suche zu optimieren, indem Sie einen Teilstring Suche in den Datenspeicher, um die Menge der übertragenen Daten so viel wie möglich zu reduzieren.

Beispiel 2:

Wenn ich "Fehler foo" fangen will, "Fehlerbalken", "Fehler baz", ich

error: (foo|bar|baz) 

und sende

search "error: " 

angeben kann in den Datenspeicher und dann erneut die zurückgegebenen Elemente.

Danke!

Answer 1

Im Allgemeinen könnten Sie versuchen, die Regex auf alle nicht eindeutigen ((a | b), [ab]) - Übereinstimmungen aufzuteilen und dann nach der längsten Zeichenfolge im resultierenden Array zu suchen. So etwas wie

$foo = longest(regex_split($regex, '(\(.*?\|.*?\))|(\[.*?\])')); 

Answer 2

Vielleicht RE auf einen endlichen Automaten umwandeln und sucht den längsten Teil, der in einem Weg zwischen Start vorhanden sein muss und beenden Staaten ... Geometrische Denken mit einer Grafik können Sie einfacher sein, zumindest ist es in meinem Fall.