Pull to refresh

Comments 1

Кажется, что можно весьма универсально прогонять регулярные выражения по всем суффиксам, если использовать их представление в виде детерминированных конечных автоматов.

Пусть, например, из начального состояния выводят рёбра с буквами a и b (например, регулярка начинается с [ab]). Переходим по каждому из рёбер, находя (двумя бинарными поисками на ребро) диапазоны подходящих суффиксов. Запишем в состояние, в которое мы пришли по ребру a, диапазон суффиксов, начинающихся с a, в состояние, в которое мы пришли по ребру b — диапазон суффиксов, начинающихся с b (если это то же самое состояние, то можно держать в нём список диапазонов). И так идём дальше по рёбрам.

Итого алгоритм такой: если есть ребро из состояния q1 в состояние q2, то берём все диапазоны, записанные в q1, находим в каждом очередной поддиапазон, записываем список из непустых полученных поддиапазонов в q2 (или дописываем в q2, если мы уже посещали это состояние), опционально объединяем смежные/пересекающиеся диапазоны, идём дальше. Проходим так по всем рёбрам от начальных состояний до конечных. Вуаля, универсальный и, кажется, оптимальный алгоритм.
Only those users with full accounts are able to leave comments. Log in, please.

Information

Founded
Location
Россия
Website
wunderfund.io
Employees
11–30 employees
Registered