Czy mają wzory patologiczne Lua z wykładniczym czasem działania?

Question

Wiadomo, że wyrażenia regularne zaimplementowane w sposób rekurencyjny (zamiast NFA/DFA) mogą w niektórych przypadkach wymagać czasu wykładniczego. Wzory Lua są implementowane za pomocą rekursywnego matchera (pozwalają na cofanie), ale są mniej wydajne niż wyrażenia regularne (zapominając o wzorze% b).

Wzorce Can Lua potrzebują czasu wykładniczego? Bez backtrackingu (jakiekolwiek wystąpienie% 0,% 1,% 2 ... pattern)? Jeśli tak, doceniam kilka przykładów.

Answer 1

Tak, wzory lua mogą mieć czas wykładniczy. Spróbuj uruchomić:

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

Mogą nadal działać dość szybko, jeśli zachowasz proste wzorce, więc spróbuję przetestować prawdziwe przykłady na twoich danych.