Hanno pattern patologici Lua con tempo di esecuzione esponenziale?

Question

Si sa che le espressioni regolari implementate in modo ricorsivo (invece di un NFA/DFA) possono richiedere in alcuni casi un tempo di esecuzione esponenziale. I pattern Lua sono implementati tramite un match ricorsivo (consentono il backtracking), ma sono meno potenti delle espressioni regolari (dimenticando il pattern% b).

I modelli Lua possono richiedere un tempo di esecuzione esponenziale? E senza retrocedere (qualsiasi occorrenza di% 0,% 1,% 2 ... modello)? Se è così, apprezzerò alcuni esempi.

Answer 1

Sì, i modelli lua possono richiedere tempi esponenziali. Provare a eseguire:

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

possono ancora funzionare ragionevolmente veloce se si tengono i modelli semplici anche se così vorrei provare testare alcuni esempi reali sui propri dati.