Topic: Fast search in the list wildcard-corrected
Greetings! Prompt, please, good (i.e. effective in respect of speed) algorithm for the following task. On a function input the text line moves. It is necessary to check up, whether it coincides on a mask with at least single line from the list of rules. Each rule is a text line which can contain a wildcard-symbol *. I Will give an example: Input: /path/hello.txt Rules: *.pdf; *.txt; *someapp *;*path*/*ello* (here there will be coincidence on *.txt and on *path*/*ello *) we Assume that such checks are fulfilled many once a second, and the list corrected contains thousand and even millions elements. It would be desirable not to transit under all list, and to use something like binary search. The list corrected is formed dynamic, in a program operating time, therefore to build of it any precompiled model it is impossible. Also it is impossible to use means with dynamic code generation (JIT, etc.) - Such restrictions of the environment. It would be desirable to find not so much implementation (a C/C ++), how many the description of the algorithm. Thanks!