From time to time I stumble across a problem of matching hashmap keys to a regular expression. In such situations I am forced to loop through all of map's elements and try to match every single key to the regex. With regex compiled to DST it should have complexity class of O(n * m) where n is number of elements in map and m is the length of the longest key in the map. Assuming m is reasonably small, we can assume it is O(n).
Above solution to this problem, although it is reasonably good, makes me think every time - is it possible to construct a data structure that would be faster (at least in theory) in searching all the keys that match the given regex. Probably it would not be linearly dependent on the number of the keys in the data structure. Is it possible? If it is possible - what would be the main idea reducing complexity?