घातीय चलने वाले समय के साथ लुआ रोगजनक पैटर्न है?

Question

यह ज्ञात है कि एक पुनरावर्ती फैशन (एनएफए/डीएफए के बजाय) में लागू नियमित अभिव्यक्तियों को कुछ मामलों में घातीय चलने वाले समय की आवश्यकता हो सकती है। लुआ पैटर्न एक रिकर्सिव मैचर (वे बैकट्रैकिंग की अनुमति देते हैं) के माध्यम से कार्यान्वित किए जाते हैं, लेकिन वे नियमित अभिव्यक्तियों (% बी पैटर्न को भूलना) से कम शक्तिशाली होते हैं।

क्या लुआ पैटर्न को घातीय चलने वाले समय की आवश्यकता हो सकती है? और बैकट्रैकिंग के बिना (% 0,% 1,% 2 ... पैटर्न की कोई घटना)? यदि ऐसा है, तो मैं कुछ उदाहरणों की सराहना करता हूं।

Answer 1

हां, लुआ पैटर्न घातीय समय ले सकते हैं। चलाने की कोशिश करें:

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

वे अभी भी यथोचित तेजी से चला सकते हैं यदि आप पैटर्न सरल हालांकि तो मैं अपने खुद के डेटा पर कुछ वास्तविक उदाहरण के परीक्षण की कोशिश करेगा रहते हैं।