Is there an efficient implementation of a dictionary whose key is a regular expression?

Question

Python

Is there a data structure, like a dictionary, where the keys are regular expressions and the search is faster than a linear pass through all the regular expressions?
Well, or not a regular expression, but something similar to "ILIKE %some_string%" - case-insensitive substring search.

Answer 1

https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...
Well, yes, you won't do it faster than O(N). Yes, and for O (N) this can not be achieved ... you still have to look for a substring.

Answer 2

I'm certainly a beginner, but you can try to write a class-converter from a regular expression to a string and use it as a key in some kind of stl container

Answer 3

A regular expression is a special case of a state machine. You are essentially faced with the task of combining all expressions into one automaton, where the initial state is the epsilon state, i.e. into a non-deterministic state machine. From it, then it is necessary to build a deterministic KA with terminal states with the corresponding values ​​from the dictionary. In general, a rather difficult solution, but it will be faster than a linear enumeration.
Alternatively, you can combine all dictionary keys into a single regular expression like "(a1)|(a2)|...|(aN)", and then determine which of the groups will be non-empty after matching. This is essentially the same as what I wrote at the beginning, only much simpler.