Поиск по регулярным выражениям с помощью суффиксного массива

[saluev]

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

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

Итого алгоритм такой: если есть ребро из состояния q1 в состояние q2, то берём все диапазоны, записанные в q1, находим в каждом очередной поддиапазон, записываем список из непустых полученных поддиапазонов в q2 (или дописываем в q2, если мы уже посещали это состояние), опционально объединяем смежные/пересекающиеся диапазоны, идём дальше. Проходим так по всем рёбрам от начальных состояний до конечных. Вуаля, универсальный и, кажется, оптимальный алгоритм.