I think it can be done with String Automata, similar to Aho-Corasick

This is how I solved this problem:

First you need to tokenize the string with some information. Suppose given string is "1*22#55#8#*#9*". So your tokens will be "1", "22", "55", "8", "9". Now you need some additional information for each token, such as minimum number of digits required, even or odd number of digits required, length of this token etc. So for this token "55" — there should be odd number of digits before this, at least one digit required(since it's odd) etc. And for this token "9" — there should be even number of digits before this, should be at least 2 digits.

Now, for each query string, start finding substring which matches with a token with satisfying other conditions. You just pick the first substring which completely matches with a token. Then start finding next token and so on. If you can find all the tokens in a query string, then the answer is "match", otherwise "not".

You do not require any DP for this, just take the first substring that completely matches with a token and move on to the next token.

See my code for further understanding https://pastebin.com/j9eHmQAP