Как построить дерево соответствия строк из массива регулярных выражений?
У меня есть динамический (иногда изменяющийся) массив регулярных выражений, например структура пути URL:
/(home)?$-> домашний вид/news/(index)?$->/news/([a-zA-Z0-9_]+)/?$-> просмотр новостной статьи( arg_1 )/news/([a-zA-Z0-9_]+)/reply_to_comment\?(.*)-> просмотр комментариев к новостям( arg 1, arg 2 )/(.+)-> 404 просмотр( arg 1 )
Если есть столкновения, первое выражение - победитель. Например, последнее выражение соответствует всему, но в том случае, если ни одно выражение до этого не совпало. Или /news/index можно сопоставить со статьей, но индекс перед выражением статьи, поэтому он выигрывает.
Я хотел бы построить конечный автомат / дерево выражений, которое я могу использовать для сопоставления с любыми строками за O(n) времени, где n - длина строки, с которой выполняется сопоставление, то есть меня не волнует время, необходимое для построения этого дерева, но я хочу иметь одинаковую скорость сопоставления независимо от количества выражений.
Или хотя бы для "ограниченного" регулярного выражения, поддерживающего только: +, *, ?, [], [^ ], (), $, Лечи каждое выражение expr не начиная с ^ как будто это было написано как ^expr,