Haben Lua pathologische Muster mit exponentieller Laufzeit?

Question

Es ist bekannt, dass reguläre Ausdrücke, die rekursiv (anstelle eines NFA/DFA) implementiert werden, in einigen Fällen eine exponentielle Laufzeit benötigen können. Lua-Muster werden über einen rekursiven Matcher implementiert (sie ermöglichen das Zurückverfolgen), aber sie sind weniger leistungsfähig als reguläre Ausdrücke (wobei% b pattern vergessen wird).

Können Can Lua-Muster eine exponentielle Laufzeit benötigen? Und ohne Backtracking (jedes Vorkommen von% 0,% 1,% 2 ... Muster)? Wenn dem so ist, werde ich einige Beispiele schätzen.

Answer 1

Ja, Lua-Muster können exponentielle Zeit benötigen. Versuchen Sie laufen:

string.find('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 
    'a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?' 
    .. 'a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa') 

Sie können immer noch recht schnell laufen, wenn Sie die Muster einfach zu halten, obwohl so würde ich versuchen, einige konkrete Beispiele auf Ihre eigenen Daten zu testen.