Какое самое длинное возможное регулярное выражение в полиномиальном времени?

Question

Вопрос Сложность подстановки регулярных выражений близок к вопросу, но это не то же самое. Согласно ответу компании, сложность (механизма DFA):

O (2 ^ m + n) [где m - длина регулярного выражения, а n - длина строки]

В Красной книге «Руководство по проектированию алгоритмов» на стр. 15-16 обсуждается время для разных алгоритмов. Согласно этому, когда длина алгоритма превышает 1 000 000, алгоритм O (m ^ 2) безнадежен. Обработка занимает 16,7 минут, при условии, что время работы составляет одну наносекунду.

Утверждение в книге увеличило мой интерес. Можете ли вы сделать Regex длиной 1 000 000 символов за 16,7 минут? Можете ли вы сделать катастрофическое регулярное выражение и время обработки все еще держится? Я действительно сомневаюсь в этом.

Какое самое длинное из возможных регулярных выражений со временем работы одной наносекунды за полиномиальное время?

Answer 1

Это бессмысленный вопрос. Регулярные выражения - это не алгоритм, а язык. Существует много реализаций этого языка, каждый из которых имеет свои собственные характеристики производительности, и каждое отдельное регулярное выражение имеет свои собственные затраты. Например, чередование /(a|b|c)/ является проблемой распараллеливания, поэтому на механизмах, которые выполняют выражение параллельно, производительность будет лучше, чем на тех, которые этого не делают.

Это похоже на вопрос о том, как лучше всего сортировать. Некоторые люди скажут вам O(n log n), но они будут неправы. Там ответ зависит от используемого алгоритма. Есть некоторые виды (например, radix sort ), которые имеют худший случай O(n).

Answer 2

Фактическая сложность, вероятно, зависит от конкретного регулярного выражения. Простое совпадение для 1000000 'a занимает около 10 секунд:

import re

expr = 'a' * 1000000
re.match(expr, expr)

Кажется, что сложность в этом случае составляет около O (m), но более сложные выражения, несомненно, потребуют больше времени.