Üstel çalışma süresi ile Lua patolojik desenleri var mı?

Question

Yinelemeli olarak (NFA/DFA yerine) uygulanan düzenli ifadelerin bazı durumlarda üssel çalışma süresine ihtiyaç duyduğu bilinmektedir. Lua desenleri, tekrarlayıcı bir eşleştirici (geri izlemeye izin verir) aracılığıyla uygulanır, ancak normal ifadelerden daha az güçlüdür (% b şablonunu unutma).

Can Lua desenleri üstel bir çalışma süresine ihtiyaç duyar mı? Ve geri izlemeden (herhangi bir% 0,% 1,% 2 ... desen) oluşumu olmadan? Eğer öyleyse, bazı örnekleri takdir edeceğim.

Answer 1

Evet, lua desenleri üstel zaman alabilir. çalıştırmayı deneyin: Eğer ben kendi verileri üzerinde bazı gerçek örnekler test denemek istiyorum gerçi basit desenleri tutarsanız

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

Onlar hala oldukça hızlı çalışabilir.