Есть ли у Lua патологические паттерны с экспоненциальным временем выполнения?

Question

Есть ли у Lua патологические паттерны с экспоненциальным временем выполнения?

Известно, что регулярные выражения, реализованные рекурсивным способом (вместо NFA/DFA), могут в некоторых случаях требовать экспоненциального времени выполнения. Шаблоны Lua реализуются с помощью рекурсивного средства сопоставления (они позволяют возвращать данные), но они менее мощны, чем регулярные выражения (забывая шаблон%b).

Могут ли паттерны Lua экспоненциально работать? И без возврата (любое вхождение шаблона%0, %1, %2...)? Если это так, я буду признателен за некоторые примеры.

4

lua time-complexity lua-patterns

Источник

user3368561 29 янв '15 в 13:18

1 ответ

Решение

Другие вопросы по тегам lua time-complexity lua-patterns

user298029 29 янв '15 в 18:17 2015-01-29 18:17 · Accepted Answer · 2015-01-29 18:17

Да, шаблоны Луа могут занять экспоненциальное время. Попробуйте запустить:

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

Они по-прежнему могут работать достаточно быстро, если вы будете придерживаться простых шаблонов, поэтому я попробую протестировать некоторые реальные примеры на ваших собственных данных.